perm filename ALLCON[DIS,DBL]4 blob
sn#226053 filedate 1976-07-19 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00084 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00007 00002 .ASEC(AM's Concepts)
C00010 00003 .ASSEC(Initial Concepts)
C00013 00004 .INDEXCPAGE←PAGE INDXP: PAGE
C00014 00005 .ASSECG(Anything)
C00016 00006 .ASSECG(Any-concept)
C00018 00007 .ASSECG(Active)
C00020 00008 .ASSECG(Object)
C00022 00009 .ASSECG(Relation)
C00023 00010 .ASSECG(Logical-combination)
C00024 00011 .ASSECG(Structure)
C00026 00012 .ASSECG(Structure-of-Structures)
C00028 00013 .ASSECG(Ord-Structure)
C00029 00014 .ASSECG(Unord-Structure)
C00030 00015 .ASSECG(Multiple-elements-structure)
C00032 00016 .ASSECG(No-multiple-elements-structure)
C00033 00017 .ASSECG(Empty-structure)
C00034 00018 .ASSECG(Nonempty-structure)
C00035 00019 . ASSECG(Sets)
C00038 00020 . ASSECG(Bags)
C00040 00021 . ASSECG(Lists)
C00042 00022 . ASSECG(Ordered-pairs)
C00045 00023 . ASSECG(Osets)
C00047 00024 .ASSECG(Insert)
C00049 00025 . ASSECG(Set-insert)
C00052 00026 . ASSECG(Oset-insert)
C00055 00027 . ASSECG(List-insert)
C00057 00028 . ASSECG(Bag-insert)
C00059 00029 .ASSECG(Delete)
C00062 00030 . ASSECG(Set-Delete)
C00064 00031 . ASSECG(Bag-Delete)
C00066 00032 . ASSECG(List-Delete)
C00068 00033 . ASSECG(Oset-Delete)
C00071 00034 .ASSECG(Intersect)
C00073 00035 . ASSECG(List-Intersect)
C00075 00036 . ASSECG(Oset-Intersect)
C00078 00037 . ASSECG(Set-Intersect)
C00081 00038 . ASSECG(Bag-Intersect)
C00083 00039 .ASSECG(Union)
C00085 00040 . ASSECG(List-Union)
C00087 00041 . ASSECG(Oset-Union)
C00089 00042 . ASSECG(Set-Union)
C00091 00043 . ASSECG(Bag-Union)
C00093 00044 .ASSECG(Difference)
C00095 00045 . ASSECG(List-Diff)
C00097 00046 . ASSECG(Oset-Diff)
C00099 00047 . ASSECG(Set-Diff)
C00101 00048 . ASSECG(Bag-Diff)
C00103 00049 .ASSECG(Conjecture)
C00104 00050 .ASSECG(Atom-obj)
C00106 00051 .ASSECG(Truth-value)
C00108 00052 .ASSECG(Operation)
C00111 00053 .ASSECG(Compose)
C00114 00054 .ASSECG(Canonize)
C00116 00055 .ASSECG(Coalesce)
C00120 00056 .ASSECG(Restrict)
C00122 00057 .ASSECG(Invert-an-operation)
C00124 00058 .ASSECG(Inverted-op)
C00125 00059 .ASSECG(Parallel-replace2)
C00127 00060 .ASSECG(Parallel-replace)
C00129 00061 .ASSECG(Repeat2)
C00131 00062 .ASSECG(Repeat)
C00133 00063 .ASSECG(Parallel-join2)
C00135 00064 .ASSECG(Parallel-join)
C00137 00065 .ASSECG(Reverse-ord-pair)
C00139 00066 .ASSECG(Last-element)
C00141 00067 .ASSECG(First-element)
C00143 00068 .ASSECG(All-but-the-first-element)
C00145 00069 .ASSECG(All-but-the-last-element)
C00146 00070 .ASSECG(Member)
C00148 00071 .ASSECG(Projection1)
C00150 00072 .ASSECG(Projection2)
C00151 00073 .ASSECG(Identity)
C00153 00074 .ASSECG(Predicate)
C00155 00075 .ASSECG(Object-equality)
C00157 00076 .ASSECG(Constant-predicate)
C00158 00077 .ASSECG(Constant-True)
C00159 00078 .ASSECG(Constant-False)
C00160 00079 .APART ASGOFF LASTCON: SSSECNUM LASTCON1: SSECNUM+1 END COMMENT CONCEPT LISTINGS
C00161 00080 .ASSEC(Concepts never fully implemented)
C00164 00081 .ASSECP(Concepts and Heuristics as coded in LISP)
C00166 00082 . ASSSEC(The `Compose' Concept)
C00190 00083 . SKIP TO COLUMN 1 ASSSEC(The `Osets' Concept)
C00193 00084 .ASSECP(Concepts created by AM)
C00199 ENDMK
C⊗;
.ASEC(AM's Concepts)
.TURN ON "{}"
The first part of this huge appendix (Appendix {ASECNUM}.1.2 to
{ASECNUM}.1.{[3]LASTCON}) lists the set of knowledge AM started with:
its initial concepts. It is not very readable, nor is it central to
any of the ⊗4ideas⊗* on which AM is based. The reader is therefore
warned to proceed at his own risk through this material.
Section 2 of this appendix contains a brief description of those
concepts which were only partially implemented in AM (e.g.,
"Destructive-op"). It was decided not to give each of them a full
"box" of their own.
The third part of this appendix lists a couple concepts as they were
actually coded into Lisp. The reader is shown which entry -- or
heuristic rule -- each bit of Lisp code corresponds to.
Finally, starting on page {[3]NEWCLIST}, a list is provided of some
of the concepts which AM created. This is intended not as an
exhaustive catalog, but merely to show the breadth of what was done
by AM, the smart guesses and the lunacies. This list could have been
pieced together by studying Appendix {[2] EXAM2}, wherein some
examples of AM in action are given. There the reader may dynamically
observe what kinds of concepts -- and infer what kinds of entries for
⊗4their⊗* facets -- AM was able to derive from its initial base.
.ALLCON: ASECNUM ;
.ASSEC(Initial Concepts)
<<Order these the same way as ALLHEUristics appendix. >
.TURN ON "{}"
Each concept will be listed, followed by a description of the entries
in each of its facets$$ Each of these entries was supplied by hand,
by the author. $. For each such "slot", a condensation is provided
(in English, LISP, and math notation) of all the knowledge initially
supplied to AM about that facet of that concept.
If there is any unmentioned facet for a concept, then it started out
blank. Many of the facets of the original concepts were left blank
intentionally, knowing that AM would be able to fill ⊗4them⊗* in as
well. After all, if you can fill in examples of any new concept, you
ought to be able to fill in examples of Sets!
The concepts are grouped semantically, much like the tree shown on
page {[3]TREECON}, like the order in which heuristics are listed in
Appendix {[2]ALLHEU}. This section of the appendix is prefaced by an
index which is arranged alphabetically, since the primary use of it
will probably be as an encyclopedia. When the reader encounters a
poorly-named or poorly-explained concept somewhere in the text, he
may wish to glance first at Chapter {[2]KNOWL}, page {[3]BRIEFC},
where very brief definitions of the concepts are also given
alphabetically. If that "dictionary" is insufficent, he can turn to
the appropriate page in this appendix, and see the same concept
presented in much more detail.
.INDEXCPAGE←PAGE; INDXP: PAGE;
.PAGE←PAGE+1;
.BEGIN; TURN ON "α↑↓←{}∞\→β"; INSERT INDEXC; END;
.PORTION INITCONS;
.TURN ON "{∞→";
.SELECT 1;
.SSSECNUM←SSSECNUM+1;
.IASECNUM: ASECNUM;
.ISSECNUM: SSECNUM;
.ISSSECNUM: SSSECNUM;
.SEND CONTENTS ⊂
@1 @*@7Index of Initial Concepts⊗*
. ⊃
.MTURN;
.ASGON;
.BEGIN COMMENT CONCEPT LISTINGS;
.ASSECG(Anything)
.SBOX(15,15)
MBOX Name(s): Anything, Entity, Thing, Item $
MBOX Definitions: $
MBOX Non-Recursive, Trivial, Quick: λ () T $
MBOX Specializations: Any-concept, Non-concepts $
MBOX Generalizations: none $
MBOX Examples: Anything, Any-concept $
MBOX Isa's: Any-concept $
MBOX Worth: 100 $
FBOX Interest: 5 heuristics (see Appendix {[2]ALLHEU}.{[2]A4ANYTHING}, page {[3]A4ANYTHINGI}).$$
In general, this appendix will omit heuristics. They will instead be presented
in one big collection, as the next appendix. For each concept, we will however
mention how many heuristics of each variety are present. The interested reader may
turn immediately to Appendix {[2]ALLHEU} if he desires, to see those heuristic
rules. $ %
MBOX Sugg: 5 heuristics $
FBOX In-domain-of: Delete, Insert$$
All four specializations of each of Delete (e.g., Bag-delete) and Insert
(e.g., List-insert) are also listed here. $, Member, Proj1, Proj2, Identity, Constant-pred. %
MBOX In-range-of: First-ele, Last-ele, Member, Proj1, Proj2, Identity. $
.EBOX
.ASSECG(Any-concept)
.SBOX(11,11)
MBOX Name(s): Any-concept, Any-Being, Anybody $
MBOX Definitions: $
MBOX Non-Recursive, Opaque, Quick: λ (x) FMEMB(x,Concepts) $
MBOX Non-Recursive, Opaque, Quick: λ (x) GETP(x,Name) $
MBOX Specializations: Active, Object $
MBOX Generalizations: Anything $
MBOX Examples: Anything, Any-concept, Active, Object $
MBOX Isa's: Anything, Any-concept $
MBOX Worth: 100 $
FBOX View: to view any X as if it were a Y, find an op. whose domain contains$$
That is, the domain of the operation is D1xD2xD3..., and X is a subset of some Di,
a specialization of Di. $ X, %
MBOX and whose range is contained in Y, and apply that op. to the given X. $
FBOX Fillin: 39 heuristics (see Appendix {[2]ALLHEU}.{[2]A4ANYB}, beginning on page {[3]A4ANYBINGF}).$$
As usual, the heuristics are listed in Appendix {[2]ALLHEU}, not here. But the
reader is forewarned that this concept has so many heuristics that they are
grouped by facet in the next appendix, occupying
Appendices {[2]ALLHEU}.{[2]A4ANYB}.1 through
{[2]ALLHEU}.{[2]A4ANYB}.{[2]A4ANYBLAST}, pages
{[3]A4ANYBINGF} to {[3]A4ANYBLASTP}. $ %
MBOX Check: 20 heuristics $
MBOX Interest: 21 heuristics $
MBOX Sugg: 30 heuristics $
.EBOX
.ASSECG(Active)
.SBOX(13,13)
MBOX Name(s): Active, activity, action $
MBOX Definitions: $
MBOX Sufficient, Non-Recursive, Quick: λ (x) GETP(x,Algorithms) $
MBOX Sufficient, Non-Recursive, Quick: λ (x) GETP(x,Dom/range) $
MBOX Specializations: Predicate, Relation, Operation $
MBOX Generalizations: Any-concept $
FBOX Examples: none.$$ Recall that each active will be an example of
an operation, predicate, etc., hence need not be pointed to explicitly here. $ %
MBOX Isa's: Any-concept $
MBOX In-domain-of: Constructive, Destructive, Coalesce, Compose, Restrict $
MBOX In-range-of: Compose, Coalesce, Restrict. $
MBOX Worth: 100 $
MBOX Fillin: 7 heuristics. $
MBOX Check: 4 heuristics $
MBOX Interest: 3 heuristics $
MBOX Sugg: 10 heuristics $
.EBOX
.ASSECG(Object)
.SBOX(15,15)
MBOX Name(s): Object, static concept, Passive $
FBOX Definitions: none.$$ Recall that all this means is that computationally,
any entity x is considered to be an Object iff it is an example of some
Specialization of this concept. Thus the list (3 A NIL) is an object, because
it is a List, and List is one Specialization of
Structure, and Structure is a Specialization of Object. $ %
FBOX Specializations: Structure, Atom-obj, Conjecture$$
This should be `Statement', and that concept should have Conjecture as a
specialization, along with Theorem, Falsehood, etc. This was never fully
implemented in the AM code, however. $ %
MBOX Generalizations: Any-concept $
MBOX Examples: none. $
MBOX Isa's: Any-concept $
MBOX In-domain-of: Object-equality $
MBOX Worth: 100 $
FBOX (⊗4No heuristics⊗*)$$ The paucity of heuristics here attests to the
little that structures, statements, and atoms have in common. They are merely
non-actives. There is much that does not apply to any of them (see the Active
and Operation concepts), but very few rules of thumb applicable to all 3 of
them. $ %
.EBOX
.ASSECG(Relation)
.SBOX(15,15)
MBOX Name(s): Relation, relationship. $
MBOX Definitions: none.$
MBOX Generalizations: Active $
MBOX Specializations: Logical-combination $
MBOX Worth: 100 $
MBOX View: To view an operation F as a relation, consider it as the set of all ordered $
MBOX pairs, a subset of Dom(F)xRan(F), containing <x,y> iff F.Defn(x,y). $
MBOX NOTE: This concept exists in only rudimentary form in AM at the moment. $
.EBOX
.ASSECG(Logical-combination)
.SBOX(15,15)
MBOX Name(s): Logical Combination, Boolean relation. $
MBOX Definitions: none.$
MBOX Generalizations: Relation $
FBOX Examples: Conjoin, Disjoin, Imply, Negate$$ These aren't coded separately as
concepts in AM, yet. $ %
MBOX Worth: 200 $
MBOX Check: 1 heuristic $
MBOX Interest: 3 heuristics $
MBOX Sugg: 2 heuristics $
MBOX NOTE: This concept exists in only rudimentary form in AM at the moment. $
.EBOX
.ASSECG(Structure)
.SBOX(8,8)
FBOX Name(s): Structure, Data-structure, sometimes:$$
That is, the user might erroneously type `List-structure' when he really
means any kind of structure. $ List-structure. %
MBOX Definitions: $
MBOX Necessary, Non-Recursive, Quick, Opaque: λ (x) LISTP(x) $
MBOX Specializations: Ord-struc, Unord-struc, Empty-struc, Non-empty-struc, $
MBOX Multiple-elements-struc, No-multiple-elements-struc, Struc-of-strucs. $
MBOX Generalizations: Object $
MBOX In-domain-of: Insert, Delete, Member, Empty, Nonempty, Difference, Union, Intersect, $
MBOX Parallel-replace(2), Parallel-join(2), Repeat(2). $
MBOX In-range-of: Insert, Delete, Difference, Union, Intersect. $
MBOX View: To view any entity x as a structure, insert x into an empty structure. $
MBOX Worth: 200 $
MBOX Fillin: 2 heuristics. $
MBOX Interest: 2 heuristics $
.EBOX
.ASSECG(Structure-of-Structures)
.SBOX(11,11)
MBOX Name(s): Structure-of-structures, struc-of-strucs. $
MBOX Definitions: $
MBOX Recursive: λ (S) Empty-struc.Defn(S) or $
MBOX [Structure.Defn(S) and z←Member.Alg(S) and Structure.Defn(z) and $
MBOX Structure-of-Structures.Defn(Delete.Algs(z,S))]. $
MBOX Declarative PC: λ (S) Structure.Defn(S) and (∀xεS) Structure.Defn(x). $
FBOX Specializations: none.$$
AM specialized this by replacing each of the two calls on `Structure.Defn'
inside Struc-of-strucs.Defn
by a call on the
definition of a single type of structure,
thereby creating, e.g., Bag-of-Sets, List-of-Osets, Bag-of-Primes, etc.
These specialized concepts were then kept around so, e.g., the sample traces
in Chapter {[2]RESULT} and in Appendix {[2]TRACES} sometimes refer to them.
Also, this concept and its specializations can be discovered independently by AM,
using heuristic rule number {[3]SRI1} (see Appendix {[2]ALLHEU}) to form a new
interesting type of structure.
$ %
MBOX Generalizations: Structure $
MBOX Worth: 300 $
.EBOX
.ASSECG(Ord-Structure)
.SBOX(11,11)
MBOX Name(s): Ord-struc, Ordered Structure, sometimes: List-structure. $
MBOX Definitions: none $
MBOX Specializations: Osets, Lists $
MBOX Generalizations: Structure $
MBOX In-domain-of: First-ele, Last-ele, All-but-first-ele, All-but-last-ele. $
MBOX In-range-of: All-but-first-ele, All-but-last-ele. $
MBOX View: To view any unord-struc as an ord-struc, do nothing to it, or permute it. $
MBOX Worth: 200 $
MBOX Fillin: 2 heuristics. $
MBOX Check: 2 heuristics. $
MBOX Interest: 1 heuristic $
.EBOX
.ASSECG(Unord-Structure)
.SBOX(11,11)
MBOX Name(s): Unord-struc, Unordered Structure, sometimes: Collection $
MBOX Definitions: none $
MBOX Specializations: Sets, Bags. $
MBOX Generalizations: Structure $
MBOX View: To view any ordered-struc as an unord-struc, SORT it. $
MBOX Worth: 200 $
MBOX Check: 1 heuristic. $
.EBOX
.ASSECG(Multiple-elements-structure)
.SBOX(11,11)
MBOX Name(s): Multiple-elements-structure, Mult-ele-struc, sometimes: Lists. $
MBOX Definitions: none $
MBOX Specializations: Lists, Bags $
MBOX Generalizations: Structure $
FBOX In-domain-of: none.$$ There are many special functions which can only make
sense for multiple-eles structures, e.g., Remove-α1-occurrence(x,S), versus
Remove-all-occurrences(x,S).
Such operations have not yet been coded and added to AM. $ %
MBOX View: To view any nonmult-struc as a mult-struc, do nothing to it, $
MBOX or: copy some elements inside it a random number of times. $
MBOX Worth: 200 $
MBOX Fillin: 1 heuristic. $
.EBOX
.ASSECG(No-multiple-elements-structure)
.SBOX(11,11)
MBOX Name(s): No-Multiple-elements-structure, Nonmult-struc, sometimes: Sets. $
MBOX Definitions: none $
MBOX Specializations: Sets, Ordered-sets $
MBOX Generalizations: Structure $
MBOX View: To view any mult-struc as a nonmult-struc, eliminate multiple elements. $
MBOX Worth: 200 $
.EBOX
.ASSECG(Empty-structure)
.SBOX(11,11)
MBOX Name(s): Empty-structure, Empty struc, sometimes: phi, NIL. $
MBOX Definitions: $
MBOX Nonrecursive quick opaque: λ (x) NULL(x) $
MBOX Nonrecursive: λ (x) Structure.Defn(x) and NOT(Member.Alg(x)). $
MBOX Generalizations: Structure $
MBOX View: To view any structure as an empty-structure, repeatedly apply Delete. $
MBOX Worth: 100 $
.EBOX
.ASSECG(Nonempty-structure)
.SBOX(12,12)
MBOX Name(s): Nonempty-structure, Nonempty struc, sometimes: structure $
MBOX Definitions: $
MBOX Nonrecursive quick opaque: λ (x) LISTP(x) $
MBOX Nonrecursive: λ (x) NOT(NOT(Member.Alg(x))). $
MBOX Generalizations: Structure $
MBOX In-range-of: Insert $
MBOX View: To view any structure as an Nonempty-structure, Insert it into itself. $
MBOX Worth: 100 $
.EBOX
. ASSECG(Sets)
.SETCON: PAGE;
.SBOX(12,12)
MBOX Name(s): Set, Class, Collection $
FBOX Definitions:$$ A surprising idea, which fell out naturally while
designing the entries for the definition facets of Sets, Bags, etc., is that
the differences between these structures is not in their definition so much as
in the particular operators which work on them. Thus all 4 kinds of structures
appear to have syntactically similar concepts, even including their definitions.
The reader must examine, e.g., the definition of Bag-insert and Set-insert to
discover the real differences between the
Set and Bag
structures which AM knows about. $ %
MBOX Recursive: λ (S) (S=α{α} or Set.Definition (Set-Delete.Alg(Member.Alg(S),S))) $
MBOX Recursive quick: λ (S) (S=α{α} or Set.Definition (CDR(S))) $
MBOX Quick: λ (S) (Match S with α{...α} ) $
FBOX Intuitions: none at present.$$ Several nice intuitions were originally
provided, then scrapped when ALL intuitions were excised from AM. $ %
FBOX Specializations: Set-of-structures$$
This concept was synthesized by AM, but was then left `permanently' in place. $ %
MBOX Generalizations: Unordered-Structure, No-multiple-elements-Structure $
MBOX In-domain-of: Set-union, Set-intersect, Set-difference, Set-insert, Set-delete $
MBOX In-range-of: Set-union, Set-intersect, Set-difference, Set-insert, Set-delete $
MBOX View: To view any structure as a Set, do: λ (x) Enclose-in-braces(x) $
MBOX To view any predicate as a Set, do: λ (P) S←α{α}. $
MBOX Forall x in Examples(Domain(P)): If P(x) then Set-insert.Alg(x,S). $
MBOX Worth: 400 $
MBOX Sugg: 1 heuristic. $
MBOX Interest: 1 heuristic. $
.EBOX
. ASSECG(Bags)
.SBOX(8,8)
MBOX Name(s): Bag, sometimes: Multiset, sometimes: Collection. $
MBOX Definitions: $
MBOX Recursive: λ (S) (S=( ) or Bag.Definition(Bag-delete.Alg(Member.Alg(S),S))) $
MBOX Recursive quick: λ (S) (S=( ) or Bag.Definition (CDR(S))) $
MBOX Quick: λ (S) (Match S with (...) ) $
.BNN←MYFOOT-1;
.ONCE TURN ON "↑↓_{}[]";
MBOX Specializations: Bag-of-structures⊗7↑[{BNN}]⊗* $
MBOX Generalizations: Unordered-Structure, Multiple-elements-Structure $
MBOX Worth: 400 $
MBOX In-domain-of: Bag-union, Bag-intersect, Bag-difference, Bag-insert, Bag-delete $
MBOX In-range-of: Bag-union, Bag-intersect, Bag-difference, Bag-insert, Bag-delete $
MBOX View: To view any structure as a Bag, do: λ (x) Enclose-in-parens(x) $
.EBOX
. ASSECG(Lists)
.SBOX(8,8)
MBOX Name(s): List, List-structure, Vector, Tuple, n-tuple, Sequence, Ordered-bag $
MBOX Definitions: $
MBOX Recursive: λ (S) (S=< > or List.Definition(List-Delete.Alg(Member.Alg(S),S))) $
MBOX Recursive quick: λ (S) (S=< > or List.Definition (CDR(S))) $
MBOX Quick: λ (S) (Match S with <...> ) $
MBOX Generalizations: Ordered-Structure, Multiple-elements-Structure $
MBOX Specializations: Ordered-pairs $
MBOX Worth: 400 $
FBOX In-domain-of: List-union, List-intersect, List-difference, List-insert, List-delete.$$
There are many special functions which can only make
sense for lists, e.g., this one: `Between(x,S)' which returns
a list of all elements lying after the first occurrence of x in S, but before the
second occurrence. Such operations have not yet been coded and added to AM. $ %
MBOX In-range-of: List-union, List-intersect, List-difference, List-insert, List-delete $
MBOX View: To view any structure as a List, do: λ (x) Enclose-in-angle-brackets(x) $
.EBOX
. ASSECG(Ordered-pairs)
.SBOX(8,8)
MBOX Name(s): Ord-pair, Opair, Ordered pair, 2-tuple, sometimes: i/o pair, pair. $
MBOX Definitions: $
MBOX Declarative: λ (S) There exist x and y such that S=<x,y>. $
MBOX Nonrecursive opaque: List.Definition (S) and CDR(S) and Null(CDDR(S)). $
MBOX Nonrecursive slow: λ (S) List.Definition(S), and S≠<>, and z←Member.Alg(S), $
MBOX and S←List-delete.Alg(z,S), and S≠<>, and y←Member.Alg(S), $
MBOX and List-delete.Defn(y,S,<>). $
MBOX Nonrecursive quick: λ (S) (Match S with <←x,←y> ) $
MBOX Generalizations: Lists $
MBOX Worth: 200 $
MBOX In-domain-of: Reverse-ord-pair $
MBOX In-range-of: Reverse-ord-pair $
MBOX View: To view any entity x as an ordered pair, consider the pair <x,x>. $
MBOX View: To view an example of an active concept F as an ord-pair, construct the $
MBOX pair whose first element is a list of the arguments to F $
MBOX [or: THE argument to F, if there is only one], and whose $
MBOX second element is the value of F on those arg(s). $
MBOX View: To view an (ordered) structure S as an Opair, consider the pair whose $
MBOX first element is some member of (the first member of) S, and $
MBOX whose second element is all the remaining members of S. $
MBOX View: Transform the ordered structure (a b...c) into the Opair (a b) or (a c). $
.EBOX
. ASSECG(Osets)
.SBOX(8,8)
MBOX Name(s): Oset, Oset-structure, Ordered-set, sometimes: Set. $
MBOX Definitions: $
MBOX Recursive: λ (S) (S=[ ] or Oset.Definition(Oset-Delete.Alg(Member.Alg(S),S))) $
MBOX Recursive quick: λ (S) (S=[ ] or Oset.Definition (CDR(S))) $
MBOX Quick: λ (S) (Match S with [...] ) $
MBOX Generalizations: Ordered-Structure, No-multiple-elements-Structure $
MBOX Worth: 400 $
MBOX In-domain-of: Oset-union, Oset-intersect, Oset-difference, Oset-insert, Oset-delete $
MBOX In-range-of: Oset-union, Oset-intersect, Oset-difference, Oset-insert, Oset-delete $
MBOX View: To view any structure as a Oset, do: λ (x) Enclose-in-square-brackets(x) $
.EBOX
.OSETCP: PAGE;
.ASSECG(Insert)
.SBOX(8,8)
MBOX Name(s): Insert, Insertion, sometimes: Add, Merge; $
MBOX Definitions: $
MBOX Quasi-recursive cases: λ (x,A,B) [determine the type of structure that A and $
MBOX B are, say S, then use S-insert.Defn(x,A,B)]. $
MBOX Necessary, Nonrecursive, Quick: λ (x,A,B) Member.Defn(x,B). $
MBOX Necessary Declarative: λ (x,A,B) zεB iff zεA or z=x. $
MBOX Necesary, Declarative: λ (x,A,B) [⊗6(∀aεA)(aεB)⊗*, and ⊗6(∀b≠x εB)(bεA)⊗*, and ⊗6xεB⊗*] $
MBOX Sufficient, Quick: B=Insert.Algs(x,A). $
MBOX Domain/range: <Anything, Structures α→ Structures> $
MBOX Algorithms: $
MBOX Quasi-recursive cases: λ (x,A) [determine the type of structure A is, $
MBOX say S, then use S-insert.Algs(x,A)]. $
MBOX Isa's: Operation $
MBOX Specializations: Bag-insert, Set-insert, List-insert, Oset-insert. $
MBOX Worth: 100 $
MBOX Check: 1 heuristic. $
.EBOX
. ASSECG(Set-insert)
.SBOX(8,8)
MBOX Name(s): Set-insert, Set insertion, sometimes: Insert, Tag. $
MBOX Definitions: $
MBOX Declarative Slow: λ (x,A,B) [⊗6(∀aεA)(aεB)⊗*, and ⊗6(∀b≠x εB)(bεA)⊗*, and ⊗6xεB⊗*] $
MBOX Recursive Slow: λ (x,A,B) (A={} and B={x}, or else: $
MBOX [AND: z←Member.Alg(A); Member.Defn(z,B); $
MBOX Set-insert.Defn(x,Set-delete.Alg(z,A),Set-delete.Alg(z,B)) ]) $
MBOX Recursive: λ (x,A,B) (A={} and B={x}, or else: $
MBOX [AND: z←CAR(A); Member.Defn(z,B); $
MBOX Set-insert.Defn(x,CDR(A),Set-delete.Alg(z,B)) ]) $
MBOX Declarative: λ (x,A,B) (∀z) zεB iff zεA α⊗ z=x. $
MBOX Quick: B=Set-insert.Algs(x,A). $
MBOX Domain/range: <Anything, Sets α→ Sets> $
FBOX Algorithms:$$ Actually, this operation, like all the other structural
operations, are much more sophisticated than this simple presentation implies.
In this case, if A is not supplied, AM chooses a random example of a Set and
inserts x into that set.
If x is missing,
then AM finds a random example of
Anything and inserts it into A. $ %
MBOX Non-recursive quick: λ (x,A) (if Member.Defn(x,A) then A, else MERGE(x,A))) $
MBOX Non-recursive quick: λ (x,A) (MERGE(x,A) and Elim-adjacent-mult-elements(A)) $
MBOX Recursive: λ (x,A) (if A={} then {x}, else if A={x} then A, else $
MBOX [z←CAR(A); if z=x then A, else CONS(z,Set-insert.Alg(x,CDR(A)))]). $
MBOX Generalizations: Insert $
MBOX Worth: 100 $
FBOX What:$$
The `What' facet doesn't really exist, but is occasionally present in this Appendix
for the aid of the reader.
A fuller English description of any concept can be obtained by looking in the
alphabetical summary of concepts, in Chapter {[2]KNOWL}, beginning on page
{[3]BRIEFC}. $ If x isn't already in A, then add it and re-sort the set A. %
.EBOX
. ASSECG(Oset-insert)
.SBOX(8,8)
MBOX Name(s): Oset-insert, Oset insertion, sometimes: Insert; $
MBOX Definitions: $
MBOX Delcarative Slow: λ (x,A,B) [⊗6(∀aεA)(aεB)⊗*, and ⊗6(∀b≠x εB)(bεA)⊗*, and ⊗6x=CAR(B)⊗*] $
MBOX Recursive Slow: λ (x,A,B) (A=[] and B=[x], or else: $
MBOX [AND: z←Member.Alg(A); Member.Defn(z,B); $
MBOX Oset-insert.Defn(x,Oset-delete.Alg(z,A),Oset-delete.Alg(z,B)) ]) $
MBOX Non-recursive, Quick: λ (x,A,B) (B=CONS(x,Oset-delete.Algs(x,A)). $
MBOX Quick: λ (x,A,B) (B=Oset-insert.Algs(x,A)). $
MBOX Necessary Quick: λ (x,A,B) (x=CAR(B)). $
MBOX Necessary, Declarative: λ (x,A,B) (∀z) zεB iff zεA α⊗ z=x. $
MBOX Domain/range: <Anything, Osets α→ Osets> $
MBOX Algorithms: $
FBOX Non-recursive quick: λ (x,A) (CONS(x,[if Member.Defn(x,A) then DREMOVE(x,A)$$
The INTERLISP function DREMOVE(x,A) destructively removes all occurrences of x from
the list structure A. $, %
MBOX else A])) $
MBOX Non-recursive quick: λ (x,A) (CONS(x,A) and DREMOVE(x,CDR(A))) $
MBOX Non-recursive quick: λ (x,A) (CONS(x,DREMOVE(x,A)) $
MBOX Recursive: λ (x,A) (if A=[] then [x], else if A=[x...] then A, else $
MBOX CONS(x,Oset-delete.Algs(x,A))). $
MBOX Generalizations: Insert $
MBOX Worth: 100 $
MBOX What: Eliminate x from A and add x as the first element of the oset A. $
.EBOX
. ASSECG(List-insert)
.SBOX(8,8)
MBOX Name(s): List-insert, List insertion, sometimes: Insert, sometimes: CONS; $
MBOX Definitions: $
MBOX Nonrecursive Quick: λ (x,A,B) (B=CONS(x,A)). $
FBOX Nonrecursive: λ (x,A,B) (A=CDR(B) and x=CAR(B)).$$
Here's how this would really appear in LISP: (LAMBDA (x A B)
(AND [APPLYB OBJ-EQUAL ALGS A (APPLYB ALL-BUT-FIRST-ELE ALGS B)]
[APPLYB OBJ-EQUAL ALGS x (APPLYB FIRST-ELE ALGS B)])). $ %
MBOX Quick: λ (x,A,B) (B=List-insert.Algs(x,A)). $
MBOX Necessary Quick: λ (x,A,B) (x=CAR(B)). $
MBOX Necessary Quick: λ (x,A,B) (A=CDR(B)). $
MBOX Domain/range: <Anything, Lists α→ Lists> $
MBOX Algorithms: $
MBOX Non-recursive quick: λ (x,A) CONS(x,A). $
MBOX Recursive slow: λ (x,A) (if A=<> then <x>, else $
FBOX NCONC1$$
This LISP function means `λ(S,z) add-the element z to the end of list S'.
CDR means All-but-the-first-element, CAR means The-first-element.
$(List-insert.Algs(x,All-but-last.Algs(A)),CAR(A)). %
MBOX Generalizations: Insert $
MBOX Worth: 100 $
MBOX What: Add the element x onto the front of the List A. $
.EBOX
. ASSECG(Bag-insert)
.SBOX(8,8)
MBOX Name(s): Bag-insert, Bag insertion, sometimes: Insert; $
MBOX Definitions: $
MBOX Nonrecursive Quick: λ (x,A,B) (B=SORT(CONS(x,A))). $
MBOX Quick: λ (x,A,B) (B=Bag-insert.Algs(x,A)). $
MBOX Domain/range: <Anything, Bags α→ Bags> $
MBOX Algorithms: $
MBOX Non-recursive quick: λ (x,A) MERGE(x,A). $
MBOX Non-recursive: λ (x,A) SORT(CONS(x,A)). $
MBOX Recursive slow: λ (x,A) (if A=() then (x), else $
FBOX if CAR(A)<$$
Here, `less than' means `precedes alphanumerically', using ALPHORDER. $x
then CONS(CAR(A),Bag-insert.Algs(x,CDR(A))), else CONS(x,A)). %
MBOX Generalizations: Insert $
MBOX Worth: 100 $
MBOX What: Merge the element x into the Bag A. $
.EBOX
.ASSECG(Delete)
.SBOX(8,8)
MBOX Name(s): Delete, Deletion, Remove, sometimes, Subtract; $
MBOX Definitions: $
MBOX Quasi-recursive cases: λ (x,A,B) [determine the type of structure A and $
MBOX B are, say S, then use S-Delete.Defn(x,A,B)]. $
FBOX Slow$$
The List-delete definitions and algorithms are relatively slow, since x might
occur anywhere in A, and it might occur more than once.
Special tricks are available to speed up the other kinds of deletions.
For Set-delete and Oset-delete, we can use DREMOVE, since deleting all
occurrences of x is fine -- there can only be at most one occurrence. For
Bag-delete, we can walk down the bag and quit when any element is seen
to be alphabetically-greater-than x. These speed-ups are the reason for maintaining
four separate kind of deletion operations.
$: λ (x,A,B) List-delete.Defn(x,A,B) %
MBOX Sufficient, Nonrecursive, Quick: λ (x,A,B) NOT(Member.Defn(x,B)). $
MBOX Sufficient, Quick: B=Delete.Algs(x,A). $
MBOX Domain/range: <Anything, Structures α→ Structures> $
MBOX Algorithms: $
MBOX Quasi-recursive cases: λ (x,A) [determine the type of structure A is, $
MBOX say S, then use S-Delete.Algs(x,A)]. $
MBOX Slow: λ (x,A) List-delete.Algs(x,A). $
MBOX Isa's: Operation $
MBOX Specializations: Set-delete, List-delete, Oset-delete, Bag-delete. $
MBOX Worth: 100 $
MBOX What: Remove (one occurrence of) x from (the front of) structure A. $
.EBOX
. ASSECG(Set-Delete)
.SBOX(8,8)
MBOX Name(s): Set-Delete, Set Deletion, sometimes: Delete; $
MBOX Definitions: $
MBOX Declarative Slow: λ (x,A,B) ⊗6(∀aεA)(aεB xor a=x) ∧ (∀bεB)(bεA) ∧ ¬xεB⊗* $
MBOX Recursive Slow: λ (x,A,B) (A={} and B={}, or else A={x} and B={}, or else: $
MBOX [AND: z←Member.Alg(A) until z⊗6≠⊗*x; Member.Defn(z,B); $
MBOX Set-Delete.Defn(x,Set-delete.Alg(z,A),Set-delete.Alg(z,B)) ]) $
MBOX Quick: B=Set-Delete.Algs(x,A). $
MBOX Domain/range: <Anything, Sets α→ Sets> $
MBOX Algorithms: $
MBOX Non-recursive quick: λ (x,A) DREMOVE(x,A) $
MBOX Non-recursive quick: λ (x,A) (if NOT(Member.Defn(x,A)) then A, $
MBOX else DREMOVE(x,A))) $
MBOX Recursive: λ (x,A) (if A={} then {}, else if A={x} then {}, else $
MBOX [z←CAR(A); if z=x then CDR(A), else CONS(z,Set-Delete.Alg(x,CDR(A)))]). $
MBOX Generalizations: Delete $
MBOX Worth: 100 $
MBOX What: remove the element x from the set S, if it's there initially. $
.EBOX
. ASSECG(Bag-Delete)
.SBOX(8,8)
MBOX Name(s): Bag-Delete, Bag Deletion, sometimes: Delete; $
MBOX Definitions: $
MBOX Recursive Slow: λ (x,A,B) (A=() and B=(), or else (A=(x...) and B=CDR(A), $
MBOX or else Bag-delete.Defn(x,CDR(A),CDR(B). $
MBOX Quick: B=Bag-Delete.Algs(x,A). $
MBOX Domain/range: <Anything, Bags α→ Bags> $
MBOX Algorithms: $
FBOX Non-recursive quick opaque$$
This algorithm is labelled Opaque because it contains very tight `sneaky' code,
implementing a highly non-standard linked data structure deletion algorithm.
The call on the Interlisp function MEMBER binds z
to the tail of A, beginning with the first occurrence of x.
$: λ (x,A) [z←(MEMBER(x,A); %
MBOX RPLACA(z,CADR(z)); RPLACD(z,CDDR(Z))] $
MBOX Recursive: λ (x,A) (if A=() then (), else if CAR(A)=x then CDR(A), else $
MBOX CONS(CAR(A),Bag-Delete.Alg(x,CDR(A)))). $
MBOX Generalizations: Delete $
MBOX Worth: 100 $
MBOX What: remove one copy of x from the Bag A, if x was int there initially. $
.EBOX
. ASSECG(List-Delete)
.SBOX(8,8)
MBOX Name(s): List-Delete, List Deletion, sometimes: Delete; $
MBOX Definitions: $
MBOX Recursive Slow: λ (x,A,B) (A=<> and B=<>, or else CAR(A)=x and CDR(A)=B, $
MBOX or else List-delete.Defn(x,CDR(A),CDR(B). $
MBOX Quick: B=List-Delete.Algs(x,A). $
MBOX Domain/range: <Anything, Lists α→ Lists> $
MBOX Algorithms: $
FBOX Non-recursive quick opaque: λ (x,A) FRPLACD(z←(MEMBER(x,A),CDDR(Z)) %
MBOX Recursive: λ (x,A) (if A=<> then <>, else if CAR(A)=x then CDR(A), else $
MBOX CONS(CAR(A),List-Delete.Alg(x,CDR(A)))). $
MBOX Generalizations: Delete $
MBOX Worth: 100 $
MBOX What: remove the first copy of x from the List A, if x is in A. $
.EBOX
. ASSECG(Oset-Delete)
.SBOX(8,8)
MBOX Name(s): Oset-Delete, Oset Deletion, sometimes: Delete; $
MBOX Definitions: $
MBOX Recursive Slow: λ (x,A,B) (A=[] and B=[], or else CAR(A)=x and CDR(A)=B, $
MBOX or else Oset-delete.Defn(x,CDR(A),CDR(B). $
MBOX Recursive Slow: λ (x,A,B) (A=[] and B=[], or else A=[x] and B=[], or else: $
MBOX [AND: z←Member.Alg(A) until z⊗6≠⊗*x; Member.Defn(z,B); $
MBOX Set-Delete.Defn(x,Set-delete.Alg(z,A),Set-delete.Alg(z,B)) ]) $
MBOX Necessary Quick: λ(x,A,B) (CAR(A)=CAR(B) xor CAR(A)=x). $
MBOX Quick: B=Oset-Delete.Algs(x,A). $
MBOX Domain/range: [Anything, Osets α→ Osets] $
MBOX Algorithms: $
FBOX Non-recursive quick opaque: λ (x,A) DREMOVE(x,A). %
FBOX Non-recursive quick opaque: λ (x,A) FRPLACD(z←(MEMBER(x,A),CDDR(z)) %
MBOX Recursive: λ (x,A) (if A=[] then [], else if CAR(A)=x then CDR(A), else $
MBOX CONS(CAR(A),Oset-Delete.Alg(x,CDR(A)))). $
MBOX Non-recursive quick: λ (x,A) (if NOT(Member.Defn(x,A)) then A, $
MBOX else DREMOVE(x,A))) $
MBOX Non-recursive quick: λ (x,A) DREMOVE(x,A) $
MBOX Recursive: λ (x,A) (if A=[] then [], else if A=[x] then [], else $
MBOX [z←CAR(A); if z=x then CDR(A), else $
MBOX if z>x then A, else Oset-Delete.Alg(x,CDR(A)))]). $
MBOX Generalizations: Delete $
MBOX Worth: 100 $
MBOX What: remove the element x from the Oset A, if it's present there initially. $
.EBOX
.ASSECG(Intersect)
.SBOX(8,8)
MBOX Name(s): Intersect, Intersection, sometimes: Product; $
MBOX Definitions: $
MBOX Quasi-recursive cases: λ (A,B,C) [determine the type of structure A and $
MBOX B are, say S, then use S-Intersect.Defn(A,B,C)]. $
MBOX Slow: λ (A,B,C) List-intersect.Defn(A,B,C) $
MBOX Necessary, Nonrecursive: λ (A,B,C) Member.Defn(x,C) iff $
MBOX Member.Defn(x,A) and Member.Defn(x,B). $
MBOX Quick: C=Intersect.Algs(A,B). $
MBOX Domain/range: <Structures Structures α→ Structures> $
MBOX Algorithms: $
MBOX Quasi-recursive cases: λ (A,B) [determine the type of structure A and B are, $
FBOX say S,$$
S might be `Sets', or S can be `Lists', etc.
$ then use S-Intersect.Algs(A,B)]. %
MBOX Slow: λ (A,B) List-Intersect.Algs(A,B). $
MBOX Isa's: Operation $
MBOX Specializations: Set-intersect, Bag-intersect, List-intersect, Oset-intersect. $
MBOX Worth: 100 $
.EBOX
. ASSECG(List-Intersect)
.SBOX(8,8)
MBOX Name(s): List-Intersect, List-Intersection, sometimes: Intersect. $
MBOX Definitions: $
MBOX Recursive slow: λ (A,B,C) if A=<> then C=<>, else $
MBOX if Member.Defn(CAR(A),B) then [CAR(A)=CAR(C) and $
MBOX List-intersect.Defn(CDR(A),List-delete.Alg(CAR(A),B),CDR(C))], else $
MBOX List-intersect.Defn(CDR(A),B,C). $
MBOX Quick: C=List-Intersect.Algs(A,B). $
MBOX Domain/range: <Lists Lists α→ Lists> $
MBOX Algorithms: $
MBOX Non-recursive: λ (A,B) [for each x in A (in order), do the following: $
MBOX if Member.Defn(x,B) then List-delete.Alg(x,B), else List-delete.Alg(x,A). $
MBOX Finally, return the value of `A' as the result. $
MBOX Recursive: λ (A,B) if A=<> then <>, else if Member.Defn(CAR(A),B) $
MBOX then CONS(CAR(A),List-intersect.Alg(CDR(A),List-delete.Alg(CAR(A),B))), $
MBOX else List-intersect.Alg(CDR(A),B). $
MBOX Generalizations: Intersect $
MBOX Worth: 100 $
MBOX What: Move along list A. Remove it (once) from B if it's there, else from A. Return A. $
.EBOX
. ASSECG(Oset-Intersect)
.SBOX(8,8)
MBOX Name(s): Oset-Intersect, Oset-Intersection, sometimes: Intersect. $
MBOX Definitions: $
FBOX Recursive$$
The difference between this definition and the similar one for List-intersect is
that here we can use the very fast DREMOVE algorithm stored in Oset-Delete.Alg,
whereas for lists it was necessary to use a slow List-delete algorithm.
$: λ (A,B,C) if A=[] then C=[], else %
FBOX if CAR(A)ε$$
To save space, we may henceforth write `xεB' to mean `Member.Defn(x,B)'.
$B then [CAR(A)=CAR(C) and %
MBOX Oset-intersect.Defn(CDR(A),Oset-delete.Alg(CAR(A),B),CDR(C))], else $
MBOX Oset-intersect.Defn(CDR(A),B,C). $
MBOX Quick: C=Oset-Intersect.Algs(A,B). $
MBOX Once Early Quick Opaque: λ (A,B,C) if B is shorter than A, $
MBOX then Oset-intersect.Defn(B,A,C). $
MBOX Domain/range: <Osets Osets α→ Osets> $
MBOX Algorithms: $
MBOX Once Early Quick Opaque: λ (A,B) if B is shorter than A, $
MBOX then Oset-intersect.Alg(B,A). $
MBOX Non-recursive: λ (A,B) [for each x in A (in order), do the following: $
MBOX if x⊗6¬ε⊗*B then DREMOVE(x,A). Finally, return the value of A. $
MBOX Non-recursive: λ (A,B) [for each x in A (in order), do the following: $
MBOX if x⊗6ε⊗*B then Oset-delete.Alg(x,B), else Oset-delete.Alg(x,A). $
MBOX Finally, return the value of `A' as the result. $
MBOX Recursive: λ (A,B) if A=[] then [], else if CAR(A)⊗6ε⊗*B $
MBOX then CONS(CAR(A),Oset-intersect.Alg(CDR(A),Oset-delete.Alg(CAR(A),B))), $
MBOX else Oset-intersect.Alg(CDR(A),B). $
MBOX Generalizations: Intersect $
MBOX Worth: 100 $
MBOX What: Move along Oset A, eliminating elements not found in Oset A. $
.EBOX
. ASSECG(Set-Intersect)
.SBOX(8,8)
MBOX Name(s): Set-Intersect, Set-Intersection, sometimes: Intersect. $
MBOX Definitions: $
MBOX Once Early Quick Opaque: λ (A,B,C) if B is shorter than A, $
MBOX then Set-intersect.Defn(B,A,C). $
MBOX Recursive: λ (A,B,C) if A={} then C={}, else $
MBOX z←Some-memb.Alg(A); $
MBOX If Member.Defn(z,B) $
MBOX then [Member.Defn(z,C) and Set-intersect.Defn(Set-delete.Alg(z,A), $
MBOX Set-delete.Alg(z,B), $
MBOX Set-delete.Alg(z,C))] $
MBOX else Set-intersect.Defn(Set-delete.Alg(z,A),B,C). $
MBOX Nonrecursive Declarative: For all ⊗6x, xεC iff xεA and xεB⊗*. $
MBOX Quick: C=Set-Intersect.Algs(A,B). $
MBOX Domain/range: <Sets Sets α→ Sets> $
MBOX Algorithms: $
MBOX Once Early Quick Opaque: λ (A,B) if B is shorter than A, $
MBOX then Set-intersect.Alg(B,A). $
MBOX Non-recursive: λ (A,B) [for each x in A, do the following: $
MBOX if x⊗6¬ε⊗*B then DREMOVE(x,A). Finally, return the value of A. $
MBOX Recursive: λ (A,B) if A={} then {}, else if CAR(A)⊗6ε⊗*B $
MBOX then CONS(CAR(A),Set-intersect.Alg(CDR(A),Set-delete.Alg(CAR(A),B))), $
MBOX else Set-intersect.Alg(CDR(A),B). $
MBOX Generalizations: Intersect $
MBOX Worth: 100 $
MBOX What: Eliminate any elements of Set A which are absent from Set B. $
.EBOX
. ASSECG(Bag-Intersect)
.SBOX(8,8)
MBOX Name(s): Bag-Intersect, Bag-Intersection, sometimes: Intersect. $
MBOX Definitions: $
MBOX Once Early Quick Opaque: λ (A,B,C) if B is shorter than A, $
MBOX then Bag-intersect.Defn(B,A,C). $
MBOX Recursive: λ (A,B,C) if A=() then C=(), else $
MBOX z←CAR(A); If Member.Defn(z,B) then [Member.Defn(z,C) and $
MBOX Bag-intersect.Defn(CDR(A),Bag-delete.Alg(z,B),Bag-delete.Alg(z,C))] $
MBOX else Bag-intersect.Defn(CDR(A),B,C). $
MBOX Quick: C=Bag-Intersect.Algs(A,B). $
MBOX Domain/range: <Bags Bags α→ Bags> $
MBOX Algorithms: $
MBOX Once Early Quick Opaque: λ (A,B) if B is shorter than A, $
MBOX then Bag-intersect.Alg(B,A). $
MBOX Non-recursive: λ (A,B) [for each x in A, do the following: $
MBOX if x⊗6ε⊗*B then B←Bag.delete.Alg(x,B), else A←Bag-delete.Alg(x,A). $
MBOX Finally, return the value of A. $
MBOX Generalizations: Intersect $
MBOX Worth: 100 $
MBOX What: the intersection of bags A and B should contain all common elements, $
MBOX with each element occurring the ⊗4minimum⊗* number of times it occurs in A or B. $
.EBOX
.ASSECG(Union)
.SBOX(8,8)
MBOX Name(s): Union, Join, Unite, sometimes: Combine, Append, Sum. $
MBOX Definitions: $
MBOX Quasi-recursive cases: λ (A,B,C) [determine the type of structure A and $
MBOX B are, say S, then use S-Union.Defn(A,B,C)]. $
MBOX Necessary, Nonrecursive: λ (A,B,C) For all x, ⊗6xεC iff xεA or xεB⊗* $
MBOX Quick: C=Union.Algs(A,B). $
MBOX Domain/range: <Structures Structures α→ Structures> $
MBOX Algorithms: $
MBOX Quasi-recursive cases: λ (A,B) [determine the type of structure A and B are, $
FBOX say S,$$
S might be `Sets', or S can be `Lists', etc.
$then use S-Union.Algs(A,B)]. %
MBOX Quasi-recursive cases: λ (A,B) [determine the type of structure A and B are, $
MBOX say S, then do S-insert.Alg(CAR(A),Union(CDR(A),B))]. $
MBOX Isa's: Operation $
MBOX Specializations: Set-Union, Bag-Union, List-Union, Oset-Union. $
MBOX Worth: 100 $
.EBOX
. ASSECG(List-Union)
.SBOX(8,8)
MBOX Name(s): List-Union, Append, Nconc, List-join, sometimes: Union. $
MBOX Definitions: $
MBOX Recursive slow: λ (A,B,C) if A=<> then C=B, else $
MBOX CAR(A)=CAR(C) and List-union.Defn(CDR(A),B,CDR(C)). $
MBOX Quick: C=List-Union.Algs(A,B). $
MBOX Domain/range: <Lists Lists α→ Lists> $
MBOX Algorithms: $
MBOX Nonrecursive, Quick, Non-destructive, Opaque: λ (A,B) (APPEND A B). $
MBOX Nonrecursive, Quick, Destructive, Opaque: λ (A,B) (NCONC A B). $
MBOX Recursive: λ (A,B) if A=<> then B, else $
MBOX CONS(CAR(A),List-Union.Alg(CDR(A),B)). $
MBOX Generalizations: Union $
MBOX Worth: 100 $
MBOX What: Append list B to the end of list A. $
.EBOX
. ASSECG(Oset-Union)
.SBOX(8,8)
MBOX Name(s): Oset-Union, Oset-join, sometimes: Union, Append. $
MBOX Definitions: $
MBOX Recursive slow: λ (A,B,C) if A=[] then C=B, $
MBOX else CAR(A)=CAR(C) and $
MBOX Oset-union.Defn[CDR(A), $
MBOX Oset-delete.Alg(CAR(A),B), $
MBOX Oset-delete.Alg(CAR(A),C)]. $
MBOX Quick: C=Oset-Union.Algs(A,B). $
MBOX Domain/range: <Osets Osets α→ Osets> $
MBOX Algorithms: $
MBOX Nonrecursive, Quick, Non-destructive, Opaque: λ (A,B) (APPEND A B). $
MBOX Nonrecursive, Quick, Destructive, Opaque: λ (A,B) (NCONC A B). $
MBOX Recursive: λ (A,B) if A=[] then B, else $
MBOX CONS(CAR(A),Oset-Union.Alg(CDR(A),Oset-delete.Alg(CAR(A),B))). $
MBOX Generalizations: Union $
MBOX Worth: 100 $
MBOX What: Append onto Oset A any new members of Oset B. $
.EBOX
. ASSECG(Set-Union)
.SBOX(8,8)
MBOX Name(s): Set-Union, Set-join, sometimes: Union, Append. $
MBOX Definitions: $
MBOX Nonrecursive Declarative: λ (A,B,C) ⊗6∀x, xεC iff xεA or xεB⊗*. $
MBOX Recursive slow: λ (A,B,C) if A={} then C=B, else CAR(A)⊗6ε⊗*C and $
MBOX Set-union.Defn(CDR(A), $
MBOX Set-delete.Alg(CAR(A),B),Set-delete.Alg(CAR(A),C)). $
MBOX Quick: C=Set-Union.Algs(A,B). $
MBOX Domain/range: <Sets Sets α→ Sets> $
MBOX Algorithms: $
MBOX Nonrecursive, Quick, Destructive, Opaque: λ (A,B) (UNION A B). $
MBOX Nonrecursive, Quick, Non-destructive, Opaque: λ (A,B) $
MBOX (Self-intersect (APPEND A B)). $
MBOX Recursive: λ (A,B) if A={} then B, else $
MBOX Set-insert.Alg(CAR(A),Set-Union.Alg(CDR(A),Set-delete.Alg(CAR(A),B))). $
MBOX Recursive: λ (A,B) if A={} then B, else $
MBOX MERGE(CAR(A),Set-Union.Alg(CDR(A),DREMOVE(CAR(A),B))). $
MBOX Generalizations: Union $
MBOX Worth: 100 $
MBOX What: Merge into Set A any new members of Set B. $
.EBOX
. ASSECG(Bag-Union)
.SBOX(8,8)
MBOX Name(s): Bag-Union, Bag-join, sometimes: Union, Append. $
MBOX Definitions: $
MBOX Recursive slow: λ (A,B,C) if A=() then C=B, else CAR(A)⊗6ε⊗*C and $
MBOX Bag-union.Defn( $
FBOX Bag-delete.Alg(CAR(A),A),$$ Yes,
this is really the same as CDR(A), and in the other concepts in this appendix
the shorter form is the one used.
Here, we decided to show the nice, symmetric form that
AM actually contains. $ %
MBOX Bag-delete.Alg(CAR(A),B), $
MBOX Bag-delete.Alg(CAR(A),C)). $
MBOX Quick: C=Bag-Union.Algs(A,B). $
MBOX Domain/range: <Bags Bags α→ Bags> $
MBOX Algorithms: $
MBOX Recursive: λ (A,B) if A=() then B, else $
MBOX Bag-insert.Alg(CAR(A),Bag-Union.Alg(CDR(A),Bag-delete.Alg(CAR(A),B))). $
MBOX Generalizations: Union $
MBOX Worth: 100 $
MBOX What: Bag-union(A,B) contains any x belonging to either bag, with multiplicity of x $
MBOX equal to the ⊗4maximum⊗* of the multiplicity of the element x in A and in B. $
.EBOX
.ASSECG(Difference)
.SBOX(8,8)
MBOX Name(s): Difference, Structure-difference, sometimes: Minus, Subtract, Complement. $
MBOX Definitions: $
MBOX Quasi-recursive cases: λ (A,B,C) [determine the type of structure A and $
MBOX B are, say S, then use S-Diff.Defn(A,B,C)]. $
MBOX Necessary, Nonrecursive: λ (A,B,C) For all x, ⊗6xεC iff xεA and ¬xεB⊗* $
MBOX Quick: C=Difference.Algs(A,B). $
MBOX Domain/range: <Structures Structures α→ Structures> $
MBOX Algorithms: $
MBOX Quasi-recursive cases: λ (A,B) [determine the type of structure A and B are, $
MBOX say S, then use S-Diff.Algs(A,B)]. $
MBOX Quasi-recursive cases: λ (A,B) [determine the type of structure A and B are, $
MBOX say S, then do S-delete.Alg(CAR(B),Difference(A,CDR(B)))]. $
MBOX Isa's: Operation $
MBOX Specializations: Set-Diff, Bag-Diff, List-Diff, Oset-Diff. $
MBOX Worth: 100 $
.EBOX
. ASSECG(List-Diff)
.SBOX(8,8)
MBOX Name(s): List-Difference, List-diff. $
MBOX Definitions: $
MBOX Recursive slow: λ (A,B,C) if A=<> then C=<>, else $
MBOX If CAR(A)⊗6ε⊗*B then List-Diff.Defn(CDR(A),List-delete.Alg(CAR(A),B),C), $
MBOX else CAR(A)=CAR(C) and List-Diff.Defn(CDR(A),B,CDR(C)). $
MBOX Quick: C=List-Diff.Algs(A,B). $
MBOX Domain/range: <Lists Lists α→ Lists> $
MBOX Algorithms: $
MBOX Nonrecursive: λ (A,B) for x in A (in order), if x is in B, $
MBOX then use List-delete to remove an x from A and B. $
MBOX Recursive: λ (A,B) if A=<> then <>, else $
MBOX If CAR(A)⊗6ε⊗*B then List-Diff.Alg(CDR(A),List-delete.Alg(CAR(A),B)), $
MBOX else CONS(CAR(A),List-Diff.Alg(CDR(A),B)). $
MBOX Generalizations: Difference $
MBOX Worth: 100 $
MBOX What: Move x along A. If x is also in B, remove it from A and from B. $
.EBOX
. ASSECG(Oset-Diff)
.SBOX(8,8)
MBOX Name(s): Oset-Difference, Oset-diff. $
MBOX Definitions: $
MBOX Recursive slow: λ (A,B,C) if A=[] then C=[], else $
MBOX If CAR(A)⊗6ε⊗*B then Oset-Diff.Defn(CDR(A),Oset-delete.Alg(CAR(A),B),C), $
MBOX else CAR(A)=CAR(C) and Oset-Diff.Defn(CDR(A),B,CDR(C)). $
MBOX Quick: C=Oset-Diff.Algs(A,B). $
MBOX Domain/range: <Osets Osets α→ Osets> $
MBOX Algorithms: $
MBOX Nonrecursive: λ (A,B) for x in A, if x is in B, then remove x from A and B. $
MBOX Recursive: λ (A,B) if A=[] then [], else $
MBOX If CAR(A)⊗6ε⊗*B then Oset-Diff.Alg(CDR(A),Oset-delete.Alg(CAR(A),B)), $
MBOX else CONS(CAR(A),Oset-Diff.Alg(CDR(A),B)). $
MBOX Recursive: λ (A,B) if A=[] then [], else $
MBOX If CAR(A)⊗6ε⊗*B then Oset-Diff.Alg(CDR(A),B), $
MBOX else CONS(CAR(A),Oset-Diff.Alg(CDR(A),B)). $
MBOX Generalizations: Difference $
MBOX Worth: 100 $
MBOX What: Moving along A, when an element also in B is encountered, $
MBOX use Oset-delete to remove it from A and from B. $
.EBOX
. ASSECG(Set-Diff)
.SBOX(8,8)
MBOX Name(s): Set-Difference, Set-diff. $
MBOX Definitions: $
MBOX Recursive slow: λ (A,B,C) if A={} then C={}, else $
MBOX If CAR(A)⊗6ε⊗*B then Set-Diff.Defn(CDR(A),Set-delete.Alg(CAR(A),B),C), $
MBOX else CAR(A)=CAR(C) and Set-Diff.Defn(CDR(A),B,CDR(C)). $
MBOX Quick: C=Set-Diff.Algs(A,B). $
MBOX Declarative Nonrecursive: λ (A,B,C) ⊗6∀x, xεC iff xεA and ¬xεB⊗*. $
MBOX Domain/range: <Sets Sets α→ Sets> $
MBOX Algorithms: $
MBOX Nonrecursive: λ (A,B) for x in A, if x is in B, then remove x from A and B. $
MBOX Recursive: λ (A,B) if A={} then {}, else $
MBOX If CAR(A)⊗6ε⊗*B then Set-Diff.Alg(CDR(A),Set-delete.Alg(CAR(A),B)), $
MBOX else CONS(CAR(A),Set-Diff.Alg(CDR(A),B)). $
MBOX Recursive: λ (A,B) if A={} then {}, else $
MBOX If CAR(A)⊗6ε⊗*B then Set-Diff.Alg(CDR(A),B), $
MBOX else CONS(CAR(A),Set-Diff.Alg(CDR(A),B)). $
MBOX Generalizations: Difference $
MBOX Worth: 100 $
MBOX What: Members of set A which are not in Set B. $
.EBOX
. ASSECG(Bag-Diff)
.SBOX(8,8)
MBOX Name(s): Bag-Difference, Bag-diff. $
MBOX Definitions: $
MBOX Recursive slow: λ (A,B,C) if A=() then C=(), else $
MBOX If CAR(A)⊗6ε⊗*B then Bag-Diff.Defn(CDR(A),Bag-delete.Alg(CAR(A),B),C), $
MBOX else CAR(A)=CAR(C) and Bag-Diff.Defn(CDR(A),B,CDR(C)). $
MBOX Quick: C=Bag-Diff.Algs(A,B). $
MBOX Domain/range: <Bags Bags α→ Bags> $
MBOX Algorithms: $
MBOX Nonrecursive: λ (A,B) for x in A, if x is in B, then remove an x from A and B. $
MBOX Recursive: λ (A,B) if A=() then (), else $
MBOX If CAR(A)⊗6ε⊗*B then Bag-Diff.Alg(CDR(A),Bag-delete.Alg(CAR(A),B)), $
MBOX else CONS(CAR(A),Bag-Diff.Alg(CDR(A),B)). $
MBOX Recursive: λ (A,B) If B=() then A, else $
MBOX If CAR(B)⊗6ε⊗*A then Bag-diff.Alg(Bag-delete.Alg(CAR(B),A),CDR(B)), $
MBOX else Bag-diff.Alg(A,CDR(B)). $
MBOX Generalizations: Difference $
MBOX Worth: 100 $
MBOX What: Move x along Bag B, removing one copy of each x from Bag A. $
.EBOX
.ASSECG(Conjecture)
.SBOX(8,8)
MBOX Name(s): Conjecture, Conjec, Hypothesis, Guess, Observation, Thesis, Belief. $
MBOX Definitions: $
MBOX Nonrecursive, Quick: λ (x) Match x with <CONJEC: ...> $
MBOX Generalizations: Object $
FBOX In-domain-of: Prove$$
At the moment, none of these three concepts is in AM.
$, Disprove, Test %
FBOX In-range-of: none$$ Conjectures are produced by heuristic rules,
not mechanically by running some Active concept. $. %
MBOX Worth: 200. $
.EBOX
.ASSECG(Atom-obj)
.SBOX(8,8)
MBOX Name(s): Atom, Atomic object, sometimes: element. $
MBOX Definitions: $
MBOX Nonrecursive, Quick, Opaque: λ (x) ATOM(x) $
FBOX Specializations: Truth-value, Variable$$
Many of the nouns in this box are not implemented as concepts in AM;
e.g., Variable, Identifier, UNPACK, MKATOM,... $, Identifier. %
MBOX Generalizations: Object $
MBOX In-domain-of: UNPACK; NthCHAR$
MBOX In-range-of: MKATTOM, PACK; $
MBOX View: To view any structure S as an atom, apply PACK to it. $
FBOX Worth: 100. $$ The absence of any heuristics here just emphasizes
the fact that literal constants, identifiers, variables, T, etc. have very
little in common that ALL objects don't share. $ %
.EBOX
.ASSECG(Truth-value)
.SBOX(8,8)
MBOX Name(s): Truth value, Logical constant, T/F, α{T,Fα}. $
FBOX Definitions: none.$$ Since no definition is provided, AM never
generalized or specialized this concept, looked for new examples of it, etc. $ %
MBOX Examples: True (T,Y,Yes), False (NIL,F,N,No). $
MBOX Generalizations: Atom-obj $
MBOX In-domain-of: Negation $
MBOX In-range-of: all predicates; the Defn facet of each concept. $
FBOX View: to view anything x as a truth value, do: λ (x) NOT(Equality.Defn(x,NIL)).$$
Thus, as in Lisp itself, an entity is associated with False iff it is null, and
with True iff it is anything else in the world. $ %
MBOX Worth: 100. $
.EBOX
.ASSECG(Operation)
.SBOX(8,8)
MBOX Name(s): Operation, sometimes: function, mapping. $
FBOX Definitions: none.$$ Recall that all this means is that computationally,
any entity x is considered to be an Operation iff it is in Operation.Exs, or if it
is an example of
some Specialization of this concept. $ %
MBOX Specializations: Inverted-op, Composition, Canonization, $
FBOX Coalesced-op, Constructive-op$$ The concepts of Constructive
and Destructive operations are not encoded as concepts yet.
The distinction between specialization of Operation and Example of operation
is quite blurry. E.g., why not consider th class of Insertion operations a whole
specialization of Operation, instead of just an example? The decision as to what
status each operation would have was quite arbitrary, I'm afraid. $ %
MBOX Generalizations: Active $
MBOX Examples: Insert, Delete, Union, Intersect, Difference, Compose, Canonize, $
MBOX Coalesce, Identity, Proj1, Proj2, First-ele, Last-ele, All-but-first-ele, $
MBOX All-but-last-ele, Restrict, Reverse-ord-pair, Member, Invert, Repeat(2), $
MBOX Parallel-join(2), Parallel-replace(2). $
MBOX In-domain-of: Invert, Parallel-join(2), Parallel-replace(2), Repeat(2). $
MBOX In-range-of: Canonize, Invert, Parallel-join(2), Parallel-replace(2), Repeat(2) $
MBOX Worth: 100 $
MBOX Fillin: 7 heuristics. $
MBOX Check: 3 heuristics $
MBOX Interest: 11 heuristics $
MBOX Sugg: 2 heuristics $
.EBOX
.ASSECG(Compose)
.SBOX(8,8)
MBOX Name(s): Compose, Composition, sometimes: afterwards; $
MBOX Definitions: $
MBOX Declarative slow: λ (A,B,C) ⊗6∀x, C(x)=A(B(x)⊗*. $
MBOX Sufficient Nonrecursive Quick: λ (A,B,C) C has the Name `A-o-B'. $
MBOX Sufficient, Slow: Are-equivalent(C,Compose.Algs(A,B)). $
MBOX Sufficient, Quick: C=Compose.Algs(A,B). $
MBOX Domain/range: <Active Active α→ Active> $
FBOX <Operation Active α→ Operation>$$
Note that while this entry would imply that Operation.In-ran-of and
Operation.In-dom-of could both contain `Compose' as an entry, only the most
general concept (i.e., `Active') has `Compose' in its In-dom-of and
In-ran-of facets. $ %
MBOX <Predicate Active α→ Predicate> $
MBOX <Relation Relation α→ Relation> $
FBOX Algorithms: $$ An algorithm for COMPOSE is a procedure for taking a
pair of operations, i.e. a pair of concepts G and H,
and creating a new active concept F which
is defined to be their composition, whose Algorithms facet contains
`λ (x) G(H(x))',
or, more precisely, `(APPLYB G ALGS (APPLYB H ALGS x))'. $ %
MBOX Distributed: use the heuristics attached to Compose to guide the filling $
MBOX in of various facets of the new composition. $
MBOX Generalizations: Operation $
MBOX Isa's: Operation $
MBOX Worth: 300 $
MBOX Fillin: 9 heuristics. $
MBOX Check: 2 heuristic. $
MBOX Suggest: 2 heuristics. $
MBOX Interest: 11 heuristics. $
.EBOX
.COMPP: PAGE;
.ASSECG(Canonize)
.SBOX(8,8)
MBOX Name(s): Canonize, Canonicalize, Standardize, sometimes: normalize. $
MBOX Definitions: $
MBOX Slow: λ (P1,P2,F) P1 and P2 are predicates over AxA, $
MBOX and F is an operation from A to A, $
FBOX and (∀x,yεA) P1(x,y) iff P2(F(x),F(y)).$$
Some examples of this: (i) P1=Same-length, P2=Equality, F=Length, A=Lists.
(ii) P1=Reversed-at-top-level, P2=Reversed-at-all-levels, F=Reverse-each-element,
A=Lists.
(iii) P1=Reversed-at-top-level, P2=Reversed-at-all-levels, F=Hash-each-element,
A=Lists. (iv) P1=Congruent-triangles, P2=Identically-equal,
F=Translate-and-rotate-to-standard-position, A=Triangles.
The typical use for ths concept is: given P2, find P1 and F. Or: given P1 and
P2, find F. $ %
MBOX Sufficient, slow: Are-equivalent(F,Canonize.Algs(P1,P2)). $
MBOX Sufficient, quick: F=Canonize.Algs(P1,P2). $
MBOX Domain/range: <Predicate Predicate α→ Operation> $
MBOX Algorithms: $
MBOX Distributed: use the heuristics attached to Canonize to guide the filling $
MBOX in of various facets of the new canonization. $
MBOX Generalizations: Operation $
MBOX Isa's: Operation $
MBOX Worth: 200 $
MBOX Fillin: 6 heuristics. $
MBOX Suggest: 5 heuristics. $
.EBOX
.ASSECG(Coalesce)
.SBOX(8,8)
MBOX Name(s): Coalesce, Self-apply, Condense, Collapse, Argument coincidence. $
MBOX Definitions: $
MBOX Declarative slow: λ (F,G) The domain of G has been collapsed, compared to F's, $
MBOX by the removal of one domain component D, and an algorithm for G $
MBOX is just a call on F, with two arguements the same. The only constraint $
MBOX on this situation is that the domain component from which $
FBOX duplicate argument is drawn is itself a specialization of D.$$
Some examples of this:
(i) Coalesce.Defn(TIMES,Square), because TIMES.Domain/range contains
<Number Number α→ Number> and Square.Domain/range contains <Number α→ Number>, and
a definition of Square is `Times(x,x)', and clearly Number is a specialization of
Number (a vacuous specialization). So Square is a coalesced form of TIMES.
(ii) Coalesce.Defn(Insert,Self-insert), where the latter concept is defined as
Insert(S,S). The domain of Insert is Anything x Structure; the domain
of the new operation is
just Structure. This passes Coalesce.Defn because Structure is a specialization
of Anything: if we can insert ANYTHING into a structure, then certainly
it is permissable to insert a STRUCTURE into a structure.
(iii) Coalesce.Defn(Equality,Constant-T) because Equality is reflexive (x=x always).
$ %
MBOX Necessary, quick: λ (F,G) The length of each Domain/range entry for $
MBOX F is one larger than the length of each entry on G.Dom/range. $
MBOX Necessary, quick: λ (F,G) The range of both F and G are equal. $
MBOX Sufficient, slow: λ (F,G) Are-equivalent(G,Coalesce.Algs(F)). $
MBOX Sufficient, quick: λ (F,G) G=Coalesce.Algs(F). $
MBOX Domain/range: <Active α→ Active> $
MBOX <Operation α→ Operation> $
MBOX <Predicate α→ Predicate> $
MBOX Algorithms: $
MBOX Distributed: use the heuristics attached to Coalesce to guide the filling $
MBOX in of various facets of the new Coalesced concept. $
MBOX Generalizations: Operation $
MBOX Isa's: Operation $
MBOX Worth: 300 $
MBOX Fillin: 4 heuristics. $
MBOX Check: 1 heuristic. $
MBOX Suggest: 2 heuristics. $
.EBOX
.ASSECG(Restrict)
.SBOX(8,8)
MBOX Name(s): Restrict, Constrain the domain/range of an active. $
MBOX Definitions: $
FBOX Nonrecursive: λ (F,G) The domain/range of G are more restrictive$$
That is, one (or more)
component of the G.Domain/range entry is a proper specialization of
the corresponding F.Dom/ran entry, and all the other components match up
equally. $ %
MBOX than that of F, and G.Defn is just a call on F.Defn. $
MBOX Sufficient, Quick: λ (F,G) G=Restrict.Algs(F). $
MBOX Domain/range: <Active α→ Active> $
MBOX <Operation α→ Operation> $
MBOX <Predicate α→ Predicate> $
MBOX Algorithms: $
MBOX Distributed: use the heuristics attached to Restrict to guide the filling $
MBOX in of various facets of the new Restricted concept. $
MBOX Plus: an explicit little program for making the substitution $
MBOX in the Domain/range facet, which is the essence of this concept. $
MBOX Isa's: Operation $
MBOX Worth: 200 $
MBOX Fillin: 3 heuristics. $
.EBOX
.ASSECG(Invert-an-operation)
.SBOX(8,8)
MBOX Name(s): Invert, Find the inverse of an operation. $
MBOX Definitions: $
MBOX Declarative slow: λ (F,G) The domain of G is the range of F, plus all the $
MBOX domain components of F except one, D; the range of G is then D. $
MBOX The value of G.Defn(x1,...,r,...,d) must be the same as the value $
MBOX the value of F.Defn(x1,...,d,...,r), for any x1,...,d, and r. $
MBOX Necessary, quick: λ (F,G) The length of each Domain/range entry for $
MBOX F is the same as the length of each entry on G.Dom/range. $
MBOX Necessary, quick: λ (F,G) Taken as SETS, a domain/range entry from F$
MBOX and one from G are actually Equal. $
MBOX Sufficient quick: λ (F,G) G has the Name `F-inverse'. $
MBOX Quick: λ (F,G) G=Invert.Algs(F). $
MBOX Domain/range: <Operation α→ Operation> $
MBOX <Operation α→ Inverted-op> $
MBOX Algorithms: $
MBOX Distributed: use the heuristics attached to Invert to guide the filling $
MBOX in of various facets of the new Inverted concept. $
MBOX Isa's: Operation $
MBOX Worth: 300 $
MBOX Fillin: 1 heuristic. $
MBOX Suggest: 1 heuristic. $
.EBOX
.ASSECG(Inverted-op)
.SBOX(8,8)
MBOX Name(s): Inverted operation,Inverse, sometimes: converse. $
MBOX Definitions: $
MBOX Declarative slow: λ (F) For some known operation G, Invert.Defn(G,F). $
MBOX Necessary, quick: λ (F) The range of F is one single known concept. $
MBOX Sufficient quick: λ (F) F has the Name `G-inverse' for some G. $
MBOX Generalizations: Operation $
FBOX In-domain-of: Invert.$$ This just means that such operations are themselves
easily invertable. $ %
MBOX In-range-of: Invert $
MBOX Worth: 200 $
.EBOX
.ASSECG(Parallel-replace2)
.SBOX(8,8)
MBOX Name(s): Parallel-replace2, Map-replace2, Parallel-substitute. $
MBOX Definitions: $
MBOX Quick: G=Parallel-Replace2.Algs(S1,S2,F). $
MBOX Domain/range: <Type-of-structure Type-of-structure Operation α→ Operation> $
MBOX Algorithms: $
MBOX Nonrecursive: λ (S1,S2,F,G) ⊗6G is an operation whose domain is S1xS2 and $
MBOX whose range is Range(F). For any structures s1εS1, s2εS2, $
MBOX G(s1,s2) is compute by replacing each element x of s1 by the$
MBOX value of F(x,s2). Notice this means that F must be an operation $
MBOX with a domain/range entry of the form <D S2 α→ R>, where R is $
MBOX unconstrained, but D is either `Anything' or -- if S1 is $
MBOX of the form `Structure-of-E's' -- E. $
MBOX Non-recursive quick: λ (S1,S2,F) if F(x,y) doesn't depend on y, $
MBOX then just do Parallel-replace.Algs(S1,F). $
MBOX Specializations: Parallel-replace $
MBOX Isa's: Operation $
MBOX Worth: 100 $
MBOX What: create a new operation, which takes 2 structures S1 and S2, and replaces each $
MBOX member x of S1 by F(x,S2). $
.EBOX
.ASSECG(Parallel-replace)
.SBOX(8,8)
MBOX Name(s): Parallel-replace, Map-replace, Parallel-substitute, MAPCAR. $
MBOX Definitions: $
MBOX Quick: λ (S1,F,G) G=Parallel-Replace.Algs(S1,F). $
MBOX Domain/range: <Type-of-structure Operation α→ Operation> $
MBOX Algorithms: $
MBOX Nonrecursive: λ (S1,F,G) ⊗6G is an operation whose domain is S1 and $
MBOX whose range is Range(F). For any structure s1εS1, $
MBOX G(s1) is computed by replacing each element x of s1 by the $
MBOX value of F(x). Notice this means that F must be an operation $
MBOX with a domain/range entry of the form <D α→ R>, where R is $
MBOX unconstrained, but D is either `Anything' or -- if S1 is $
MBOX of the form `Structure-of-E's' -- E. $
MBOX Generalizations: Parallel-replace2 $
MBOX Worth: 100 $
FBOX Sugg: 2 heuristics.$$ These actually deal with substitution operations,
the RESULTS of applying Parallel-replace and Parallel-replace2. $ %
MBOX What: create a new operation, which takes a structures S1, and replaces each $
MBOX member x of S1 by F(x). $
.EBOX
.ASSECG(Repeat2)
.SBOX(8,8)
MBOX Name(s): Repeat2, Map-repeat2, Iterate2, Map2, MAP2CONC. $
MBOX Definitions: $
MBOX Quick: λ (S1,S2,F,G) G=Repeat2.Algs(S1,S2,F). $
MBOX Domain/range: <Type-of-structure Type-of-structure Operation α→ Operation> $
MBOX Algorithms: $
MBOX Nonrecursive: λ (S1,S2,F ⊗6G=Repeat2(S1,S2,F) is an operation whose $
MBOX domain is S1xS2 and whose range is Range(F). $
MBOX For any structures s1εS1, s2εS2, $
MBOX G(s1,s2) is computed by the following algorithm: $
MBOX y←CAR(s1); s1←CDR(s1); $
MBOX while s1 do: y←F(y,s2,CAR(s1)); s1←CDR(s1); $
MBOX Finally, return y. $
MBOX Notice this means that F must be an operation whose domain/range $
MBOX has the form <s1 S2 s1 α→ s1>. $
MBOX Non-recursive quick: λ (S1,S2,F) if F(x,y,z) doesn't depend on z, $
MBOX then just do Repeat.Algs(S1,F). $
MBOX Specializations: Repeat $
MBOX Isa's: Operation $
MBOX Worth: 100 $
MBOX What: create a new operation, which takes 2 structures S1 and S2, and repeats $
MBOX F(x,y,s2) along the members x,y of S1. $
.EBOX
.ASSECG(Repeat)
.SBOX(8,8)
MBOX Name(s): Repeat, Map, Iterate, Sequence. $
MBOX Definitions: $
MBOX Quick: λ (S1,F,G) G=Repeat.Algs(S1,F). $
MBOX Domain/range: <Type-of-structure Operation α→ Operation> $
MBOX Algorithms: $
MBOX Nonrecursive: λ (S1,F) ⊗6Repeat(S1,F)=G is an operation whose domain $
MBOX is S1 and whose range is Range(F). For any structure s1εS1, $
MBOX G(s1) is computed by the following algorithm: $
MBOX y←CAR(s1); s1←CDR(s1); $
MBOX while s1 do: y←F(y,CAR(s1)); s1←CDR(s1); $
MBOX Finally, return y. $
MBOX Notice this means that F must be an operation whose domain/range $
MBOX has the form <s1 s1 α→ s1>. $
MBOX Generalizations: Repeat2 $
MBOX Worth: 100 $
MBOX What: create a new operation which repeats F all the way along an S1. $
.EBOX
.ASSECG(Parallel-join2)
.SBOX(8,8)
MBOX Name(s): Parallel-join2, Map-join2, Parallel-union2, MAP2CONC. $
MBOX Definitions: $
MBOX Quick: λ (S1,S2,F,G) G=Parallel-join2.Algs(S1,S2,F). $
MBOX Domain/range: <Type-of-structure Type-of-structure Operation α→ Operation> $
MBOX Algorithms: $
MBOX Nonrecursive: λ (S1,S2,F,G) ⊗6G is an operation whose domain is S1xS2 and $
MBOX whose range is Range(F). For any structures s1εS1, s2εS2, $
MBOX G(s1,s2) is compute by appending together the values of F(x,s2), $
MBOX for each element x in s1. So F has to be an operation $
MBOX with a domain/range entry of the form <D S2 α→ R>, where R is $
MBOX a type of structure, but D is either `Anything' or -- if S1 is $
MBOX of the form `Structure-of-E's' -- E. $
MBOX Non-recursive quick: λ (S1,S2,F) if F(x,y) doesn't depend on y, $
MBOX then just do Parallel-join.Algs(S1,F). $
MBOX Specializations: Parallel-join $
MBOX Isa's: Operation $
MBOX Worth: 100 $
MBOX What: create a new operation, which takes 2 structures S1 and S2, and joins $
MBOX together F(x,s2) for each member x of S1. $
.EBOX
.ASSECG(Parallel-join)
.SBOX(8,8)
MBOX Name(s): Parallel-join, Map-join, Parallel-union, MAPAPPEND, MAPCONC. $
MBOX Definitions: $
MBOX Quick: λ (S1,F,G) G=Parallel-join.Algs(S1,F). $
MBOX Domain/range: <Type-of-structure Operation α→ Operation> $
MBOX Algorithms: $
MBOX Nonrecursive: λ (S1,F,G) ⊗6G is an operation whose domain is S1 and $
MBOX whose range is Range(F). For any structure s1εS1, $
MBOX G(s1) is computed by appending together the values of F(x), $
MBOX for each xεs1. Notice this means that F must be an operation $
MBOX with a domain/range entry of the form <D α→ R>, where R is $
MBOX a type of structure, and D is either `Anything' or -- if S1 is $
MBOX of the form `Structure-of-E's' -- E. $
MBOX Generalizations: Parallel-join2 $
MBOX Worth: 100 $
MBOX What: create a new operation, which takes a structure S1, and joins together $
MBOX F of each member of S1. $
.EBOX
.ASSECG(Reverse-ord-pair)
.SBOX(8,8)
MBOX Name(s): Reverse-ord-pair, Reverse ordered pair, Switch CAR and CADR. $
MBOX Definitions: $
MBOX Nonrecursive quick: λ (P,Q) First.Alg(P)=Final.Alg(Q), $
MBOX and Final.Alg(P)=First.Alg(Q). $
MBOX Quick: λ (P,Q) Q=Reverse-ord-pair.Algs(P). $
MBOX Domain/range: <Ordered-pair α→ Ordered-pair> $
MBOX Algorithms: $
FBOX Nonrecursive: λ (P) Q←P; First.Alg(Q,Final.Alg(P))$$
The expression First.Alg(A,x) will result in a RPLACA: the first element of A
will be removed, and in its place x will appear.
Thus First.Alg(<a b c d>, z) will return as its value the new list <z b c d>.
$; Final.Alg(Q,First.Alg(P)); Q. %
MBOX Nonrecursive quick opaque, nondestructive: λ (P) LIST(CADR(P),CAR(P). $
MBOX Nonrecursive quick opaque, destructive: λ (P) z←Last-ele(P); $
MBOX FRPLACA(CDR(P),CAR(P)); FRPLACA(P,z); P. $
MBOX Nonrecursive quick opaque, nondestructive: λ (P) REVERSE(P). $
MBOX Nonrecursive quick opaque, destructive: λ (P) DREVERSE(P). $
MBOX Isa's: Operation $
MBOX Worth: 100 $
MBOX What: turn the ordered pair <x,y> into the ordered pair <y,x>. $
.EBOX
.ASSECG(Last-element)
.SBOX(8,8)
MBOX Name(s): Last-element, Final member. $
MBOX Definitions: $
MBOX Recursive: λ (S,x) z←First-element.Alg(S), and S←Delete.Alg(z,S), $
MBOX and if Empty-struc.Defn(S) then x=z, else Last-element.Defn(S,x). $
MBOX Quick: λ (S,x) x=Last-element.Algs(S). $
MBOX Domain/range: <Ordered-structure α→ Anything> $
MBOX Algorithms: $
MBOX Recursive: λ (S) z←First-element.Alg(S), and S←Delete.Alg(z,S), $
MBOX and if Empty-struc.Defn(S) then z, else Last-element.Alg(S). $
MBOX Nonrecursive quick opaque: λ (S) CAR(LAST(S)). $
MBOX Isa's: Operation $
MBOX Worth: 100 $
FBOX What: find the final member of the ordered structure S.$$
Actually, this concept is much more sophisticated. If Last-element.Algs is called
with TWO arguments, S and v, then the intention is taken to be to REPLACE the
last element of S by the element v. Thus that last element is deleted, and
v is added at the end of S. This is done by: FRPLACA(LAST(S),v).
To review: Last-element.Alg(A,x) resets the final member of A to x, while
Last-element.Defn(A,x) merely tests whether the last member of A is x. $ %
.EBOX
.ASSECG(First-element)
.SBOX(8,8)
MBOX Name(s): First-element, Initial member, Head, Front element, CAR. $
MBOX Definitions: $
MBOX Recursive: λ (S,x) z←Last-element.Alg(S), and S←Delete.Alg(z,S), $
MBOX and if Empty-struc.Defn(S) then x=z, else First-element.Defn(S,x). $
MBOX Quick: λ (S,x) x=First-element.Algs(S). $
MBOX Domain/range: <Ordered-structure α→ Anything> $
MBOX Algorithms: $
MBOX Recursive: λ (S) z←Last-element.Alg(S), and S←Delete.Alg(z,S), $
MBOX and if Empty-struc.Defn(S) then z, else First-element.Alg(S). $
MBOX Nonrecursive, very quick, opaque: λ (S) CAR(S). $
MBOX Isa's: Operation $
MBOX Worth: 100 $
FBOX What: find the initial member of the ordered structure S.$$
Actually, this operation's algorithm,
if fed two arguments S and v, will replace the first element of
S by v, using FRPLACA(S,v). So this single concept contains both CAR and FRPLACA
knowledge.
This is not shown explicitly in the entries for First-element.Algs. $ %
.EBOX
.ASSECG(All-but-the-first-element)
.SBOX(8,8)
MBOX Name(s): Rear, All but the first element, All-but-first, CDR, Tail, sometimes: back. $
MBOX Definitions: $
MBOX Nonrecursive: λ (S,R) List-delete.Defn(CAR(S),S,R). $
MBOX Nonrecursive: λ (S,R) List-insert.Defn(CAR(S),R,S). $
MBOX Nonrecursive: λ (S,R) CDR(S)=R. $
MBOX Quick: λ (S,R) R=Rear.Algs(S). $
MBOX Domain/range: <Ordered-structure α→ Ordered-structure> $
MBOX Algorithms: $
MBOX Nonrecursive, very quick, opaque: λ (S) CDR(S) $
MBOX Nonrecursive: λ (S) z←First-ele.Alg(S); List-delete.Algs(z,S). $
MBOX Isa's: Operation $
MBOX Worth: 100 $
MBOX What: remove the initial member of the ordered structure S.$
.EBOX
.ASSECG(All-but-the-last-element)
.SBOX(8,8)
MBOX Name(s): All-but-the-last-element, All-but-last, sometimes: front. $
MBOX Definitions: $
MBOX Quick: λ (S,R) R=All-but-last.Algs(S). $
MBOX Domain/range: <Ordered-structure α→ Ordered-structure> $
MBOX Algorithms: $
MBOX Nonrecursive, very quick, opaque: λ (S) FRPLACD(LAST(S),NIL). $
MBOX Isa's: Operation $
MBOX Worth: 100 $
MBOX What: remove the final element from the ordered structure S.$
.EBOX
.ASSECG(Member)
.SBOX(8,8)
MBOX Name(s): Some-element, Random member, Any element of, Member, In, Some-member. $
MBOX Definitions: $
MBOX Recursive: λ (x,S) Nonempty-struc.Defn(S) and $
MBOX if First-ele.Defn(S,x) then True, $
MBOX else Member.Defn(x,All-but-first-ele.Alg(S)). $
MBOX Nonrecursive quick opaque: λ (x,S) MEMBER(x,S)). $
MBOX Sufficient, very quick, opaque: λ (x,S) FMEMB(x,S)). $
MBOX Quick: λ (S,x) x=Member.Algs(S). $
MBOX Domain/range: <Structure α→ Anything> $
MBOX Algorithms: $
MBOX Nonrecursive opaque: λ (S) CAR(RAND-PERMUTE(S)). $
MBOX Nonrecursive quick opaque: λ (S) CAR(S)). $
MBOX Recursive slow: if S is empty then fail, otherwise if S=(x) then x, $
MBOX else if RAND(0,1)=1 then First-ele.Alg(S), $
MBOX else Member.Alg(All-but-last.Alg(S)). $
MBOX Isa's: Operation $
MBOX Worth: 100 $
MBOX What: find a random member of the structure S. $
.EBOX
.ASSECG(Projection1)
.SBOX(8,8)
MBOX Name(s): Projection1, First-argument, Proj1. $
MBOX Definitions: $
MBOX Nonrecursive quick: λ (x,y,...,z) z=x $
MBOX Quick: λ (x,y,...q,z) z=Some-element.Algs(x,y,...q). $
FBOX Domain/range: <←D Anything...Anything α→ `D'> $$ This means that
`D' can be anything, so long as it's the same in both places in the domain/range
template. Thus this includes <Sets Anything Anything α→ Sets>. $ %
MBOX Algorithms: $
MBOX Nonrecursive quick: λ (x,y,...,q) x. $
MBOX Isa's: Operation $
MBOX Specializations: Identity. $
MBOX Worth: 100 $
MBOX What: accept a bunch of arguments and return the first one. $
.EBOX
.ASSECG(Projection2)
.SBOX(8,8)
MBOX Name(s): Projection2, Second-argument, Proj2. $
MBOX Definitions: $
MBOX Nonrecursive quick: λ (x,y,...,z) z=y $
MBOX Quick: λ (x,y,...q,z) z=Some-element.Algs(x,y,...q). $
MBOX Domain/range: <Anything ←D Anything...Anything α→ `D'> $
MBOX Algorithms: $
MBOX Nonrecursive quick: λ (x,y,...,q) y. $
MBOX Isa's: Operation $
MBOX Specializations: Identity. $
MBOX Worth: 200 $
MBOX What: accept a bunch of arguments and return the second one. $
.EBOX
.ASSECG(Identity)
.SBOX(8,8)
MBOX Name(s): Identity, identity-operation, no-op, Self, no change. $
MBOX Definitions: $
MBOX Nonrecursive: λ (x,y) Equality.Defn(x,y) $
MBOX Nonrecursive transform: λ (x,y) Proj1.Defn(x,x,y) $
MBOX Nonrecursive transform: λ (x,y) Proj2.Defn(x,x,y) $
MBOX Sufficient, very quick, opaque: λ (x,y) EQ(x,y)). $
MBOX Quick: λ (x,y) y=Identity.Algs(x). $
MBOX Domain/range: <Anything α→ Anything> $
MBOX <Object α→ Object> $
MBOX <Structures α→ Structures> $
MBOX <Active α→ Active> $
MBOX Algorithms: $
MBOX Nonrecursive quick: λ (x) x. $
MBOX Nonrecursive transform: λ (x) Projection1.Algs(x,x). $
MBOX Nonrecursive transform: λ (x) Projection2.Algs(x,x). $
MBOX Conjec: `Identity, restricted to Objects, is the same as Obj-Equality.' $
MBOX Generalizations: Projection1, Projection2. $
MBOX Worth: 100 $
MBOX What: the identity operation, closely related to Equality. $
.EBOX
.ASSECG(Predicate)
.SBOX(8,8)
MBOX Name(s): Predicate, sometimes: logical operation, Boolean function. $
MBOX Definitions: $
MBOX Nonrecursive quick opaque: λ (P) Range(P) is Truth-value; i.e., α{T,Fα}. $
MBOX Generalizations: Active $
MBOX Examples: Equality, Constructive, Destructive, Empty, Nonempty, Constant-pred, $
FBOX the Defn entries of each concept.$$
Thus the predicate `Empty', while it exists in AM, is superflous, since the
definition facet of `Empty-struc' contains that very predicate. $ %
MBOX In-domain-of: Canonize $
MBOX Worth: 100 $
MBOX Fillin: 2 heuristics. $
MBOX Sugg: 1 heuristic. $
MBOX Interest: 1 heuristic. $
.EBOX
.ASSECG(Object-equality)
.SBOX(8,8)
MBOX Name(s): Equality, Object equality, Obj-equal, Equal, Same. $
MBOX Definitions: $
MBOX Nonrecursive opaque: λ (x,y) EQUAL(x,y) $
MBOX Sufficient, very quick, opaque: λ (x,y) EQ(x,y)). $
MBOX Recursive slow: λ (x,y) x and y are both identical atoms, $
MBOX or x and y are both empty structures, $
MBOX or x and y are both nonempty structures and $
MBOX Equality.Defn(CAR(x),CAR(y)) and $
MBOX Equality.Defn(CDR(x),CDR(y)). $
MBOX Nonrecursive transform slow: λ (x y) Identity.Defn(x,y). $
MBOX Quick: λ (x,y) y=Equality.Algs(x). $
MBOX Domain/range: <Object Object α→ α{T,Fα}> $
MBOX <Structure Structure α→ α{T,Fα}> $
MBOX Algorithms: $
MBOX Nonrecursive quick: λ (x) x. $
MBOX Conjec: `Identity, restricted to Objects, is the same as Obj-Equality.' $
MBOX Isa's: Predicate $
MBOX Worth: 200 $
MBOX What: the Equality of two list structures; closely related to Identity op. $
.EBOX
.ASSECG(Constant-predicate)
.SBOX(8,8)
MBOX Name(s): Constant-predicate, Const pred, Logical constant function. $
MBOX Definitions: none. $
MBOX Domain/range: <Anything... Anything α→ α{T,Fα}> $
MBOX Isa's: Predicate $
MBOX Specializations: Constant-True, Constant-False $
MBOX Conjec: (∀x,∀y) Constant-pred.Defn(x)=Constant-pred.Defn(y). $
MBOX Worth: 100 $
MBOX What: a predicate which always returns the same logical value. $
.EBOX
.ASSECG(Constant-True)
.SBOX(8,8)
MBOX Name(s): Constant-True, Constant T, Always-T, sometimes: Always. $
MBOX Definitions: $
MBOX Nonrecursive, very quick: λ (...) T. $
MBOX Domain/range: <Anything... Anything α→ α{T,Fα}> $
MBOX <Anything... Anything α→ α{Tα}> $
MBOX Generalizations: Constant-Predicate $
MBOX Worth: 100 $
MBOX What: a predicate which always returns True. $
.EBOX
.ASSECG(Constant-False)
.SBOX(8,8)
MBOX Name(s): Constant-False, Constant F, Always-F, sometimes: Never. $
MBOX Definitions: $
FBOX Nonrecursive, very quick: λ (...) F$$ Actually, the value returned
is `NIL', not False or F. $ %
MBOX Domain/range: <Anything... Anything α→ α{T,Fα}> $
MBOX <Anything... Anything α→ α{Fα}> $
MBOX Generalizations: Constant-Predicate $
MBOX Worth: 100 $
MBOX What: a predicate which always returns False. $
.EBOX
.APART; ASGOFF; LASTCON: SSSECNUM; LASTCON1: SSECNUM+1; END COMMENT CONCEPT LISTINGS;
.ASSEC(Concepts never fully implemented)
The following concepts were designed "on paper" before AM was coded,
but were never put into AM -- at least not fully. Future work on AM
may include their coding, insertion into AM, and debugging. An
asterisk (*) means that a crude, rudimentary version of the concept
was coded and placed in AM, but had little impact on its behavior.
.BEGIN INDENT 3,8,0; ONCE PREFACE 2;
⊗6Statement:⊗*: would include conjectures, theorems, axioms, hypotheses,
conclusions, relationships.
⊗6Prove, Disprove, Proof, Counterexample, Theorem, Techniques for
proving existence, Techniques for establishing universal
conjectures,...:⊗* altogether about two dozen concepts were designed.
⊗6Mathematical Induction⊗*, including double induction.
⊗6Mathematical theory, system, basis, foundation, axiom, isomorphism,...⊗*
⊗6Cause and effect:⊗* their relation to theory formation.
⊗6Variable, Assignment, Binding, Quantification, Scope,...:⊗* a dozen
concepts along these lines.
⊗6Constant, Identifier, PNAME/P2NAME,...:⊗* AM never really needed
any non-opaque information about these, although future expansion of
the system should probably include the coding and insertion of these
concepts.
⊗6Inverse-coalesce:⊗* Given an active concept F(x), replace some
occurrences of x in F.Defn by "y", thereby making a new operation
which is a function of x and y.
⊗6Negate, Conjoin, Disjoin, Imply,...⊗*: These logical operators and
relationships had too little semantic information to make it
necessary to encode each one into a concept.
.OOO
(*) ⊗6Constructive, Destructive:⊗* these two predicates would judge
any operation.
.OOO
(*) ⊗6Non-concept⊗*: All entities which are not concepts. There was
nothing to say about them, as a whole.
.E
.ASSECP(Concepts and Heuristics as coded in LISP)
.CONSEC: SSECNUM ;
.CONS: ASECNUM;
.BEGIN TURN ON "{}";
The reader may wish to inspect the actual LISP encoding of concepts
and their facets -- including heuristic rules. For that reason, a few
pages are excerpted from the AM program and shown below.
The facets of a concept are stored as properties on its property
list. Each facet has a rigid format that it must adhere to; that
format varies from facet to facet.
Two concepts have been selected: ⊗4Compose⊗*, which is larger than
the typical concept, and ⊗4Oset-structure⊗*, which is a smaller and
simpler concept.
. ASSSEC(The `Compose' Concept)
.TURN ON "{}";
Here is the property list of the atom "COMPOSE", when AM starts up.
The reader should look for (and find!) parallels between the
complete entries below and the abbreviated summaries on page {[3]COMPP}.
For that reason, after each entry, the corresponding summary line is repeated
(in a box).
.BEGIN NOFILL PREFACE 0; INDENT 0; SELECT 3; TURN OFF "@"; GROUP
⊗5↓_ENGN_↓⊗*$$ This is short for "English name", and is the facet called "Name(s)"
everywhere else in this thesis.$ (COMPOSE Compose Composition (Afterwards))
⊗4Appearance on page {[3]COMPP}:⊗*
.WBOX(8,8)
MBOX Name(s): Compose, Composition, sometimes: afterwards; $
.EBOX
.APART;
⊗5↓_DEFN_↓⊗* (TYPE NEC&SUFF PC DECLARATIVE SLOW (FOREACH X IN (DOMAIN BA2)
RETURN (APPLYB$$
The function "APPLYB" indicates that a concept's facet is to be accessed and then
executed. (APPLYB C F x y...) means: access an entry on facet F of concept C,
and then run it on the arguments x,y,... $ BA1 ALGS (APPLYB BA2 ALGS X]
↓_DEFN-SUFF_↓ [[TYPE SUFFICIENT NONRECURSIVE QUICK
(AND (ISA BA1 'ACTIVE)
(ISA BA2 'ACTIVE)
(ISA BA3 'ACTIVE)
(ARE-EQUIV BA3 (ALREADY-COMPOSED$$
This LISP function checks to see whether the two operations have been composed
before. $ BA1 BA2]
[TYPE SUFFICIENT QUASIRECURSIVE SLOW (ARE-EQUIV BA3
(APPLYB 'COMPOSE 'ALGS BA1 BA2]$$ The arguments to Compose.Defn
(and to Compose.Algs as well) are called BA1, BA2,... Thus we would write
each definition of Compose as "λ (BA1 BA2 BA3) ..." $
[TYPE SUFFICIENT QUASIRECURSIVE QUICK (EQUAL BA3
(APPLYB 'COMPOSE 'ALGS BA1 BA2]]
⊗4Appearance on page {[3]COMPP}:⊗*
.WBOX(8,8)
MBOX Definitions: $
MBOX Declarative slow: λ (A,B,C) ⊗6∀x, C(x)=A(B(x)⊗*. $
MBOX Sufficient Nonrecursive Quick: λ (A,B,C) C has the Name `A-o-B'. $
MBOX Sufficient, Slow: Are-equivalent(C,Compose.Algs(A,B)). $
MBOX Sufficient, Quick: C=Compose.Algs(A,B). $
.EBOX
.APART; GROUP;
⊗5↓_D-R_↓⊗* ((OPERATION ACTIVE OPERATION)
(RELATION RELATION RELATION)
(PREDICATE ACTIVE PREDICATE)
(ACTIVE ACTIVE ACTIVE))
↓_D-R-FILLIN1_↓ (PROGN (ARGS-ASA COMPOSE F1 F2) (CADAR (CON-MERGE-ARGS$$
This is a LISP function, opaque to AM, which analyzes the Domain/range facets
of the two operations F1 and F2, and sees how (if at all) the range of F1 can
be made to overlap the domain of F2. Note that F2 is applied AFTER F1.
The LISP code for this function is presented on page {[3]CONMERGEP}. $ F1 F2)))
↓_EXS-D-R-FILLIN1_↓ [PROGN (ARGS-ASA COMPOSE F1 F2)
[SETQ RAN1 (LAST (ANY1OF (GETB F1 'D-R] (* RAN1 is the range of F1)
[SETQ DOM1 (ALL-BUT-LAST (ANY1OF (GETB F1 'D-R]
[SETQ RAN2 (LAST (ANY1OF (GETB F2 'D-R] (* RAN2 is the range of F2)
[SETQ DOM2 (ALL-BUT-LAST (ANY1OF (GETB F2 'D-R]
[SETQ X (MAXIMAL RAN2 DOM1 'FRAC-OVERLAP]
(NCONC1 (LSUBST DOM2 for X in DOM1) RAN1]
⊗4Appearance on page {[3]COMPP}:⊗*
.WBOX(8,8)
MBOX Domain/range: <Active Active α→ Active> $
MBOX <Operation Active α→ Operation> $
MBOX <Predicate Active α→ Predicate> $
MBOX <Relation Relation α→ Relation> $
MBOX Fillin: 2 ⊗4(out of a total of 9)⊗* heuristics. $
FBOX In Appendix {[2]ALLHEU}, these are heuristics numbers {[3]CDRH1} and {[3]CDRH2}. %
.EBOX
.APART;
⊗5↓_ALGS_↓⊗* ((TYPE QUASIRECURSIVE INDIRECT CASES [PROGN
(COND
((NULL BA1)
(APPLYB 'COMPOSE
'ALGS
(RAND-MEMB (EXS$$
The function "EXS" ripples outward from its argument, collecting examples as it
goes. $ ACTIVE))
BA2 BA3 BA4))$$ Note what this clause says: if Compose.Algs
is ever called with its first argument missing, randomly select an Active to
use as that constituent of the composition. $
&$$ Similar to last case: takes care of missing second argument.
The ampersand, "&", indicates an omission from this listing. $
((ALREADY-COMPOSED BA1 BA2) (* Note: this sets GTEMP12) GTEMP12)
((AND BA1 BA2 (IS-CON$$
An abbreviation for (APPLYB 'ANY-CONCEPT 'DEFN BA1); i.e., test whether BA1
is a bona fide concept or not. $ BA1)
(IS-CON BA2)
(ISA BA1 'ACTIVE)
(ISA BA2 'ACTIVE)
(SETQ GTEMP11 (CON-MERGE-ARGS BA1 BA2 GTEMP12)))
(* GTEMP12 is now the name of the new composition)
(CREATEB$$
CREATEB is a function which sets up a new blank data structure for a new concept.
$ GTEMP12)
[SETQ GUP1 (COND ((ISAG CS-B 'COMPOSE) CS-B) (T 'COMPOSE]
(* GUP1 is now the KIND of concept which GTEMP12 is to be an example of.
This will usually be "COMPOSE" or some variant of it. )
[INCRB$$
The function call (INCRB C F X) means: add entry X to the F facet of concept C.
$ GTEMP12 'DEFN
(LIST 'TYPE 'APPLICATION 'OF GUP1
(APPEND (LIST 'APPLYB (Q$$
The LISP function "Q" is like a double quote; after one evaluation
(Q X) returns 'X; after one more evaluation, 'X returns X; after
a final evaluation, we get the VALUE of X.
$ COMPOSE) (Q ALGS) (KWOTE BA1) (KWOTE BA2))
(FIRSTN (LENGTH (CAAR GTEMP11)) BA-LIST]
(* Another way to fill in an entry for GTEMP12.Defn)
(COND
([SETQ GTEMP308 (CAR (SOME (EXS COMPOSE)
(FUNCTION (LAMBDA (C)
(MEMBER (LASTELE (GETB GTEMP12 'DEFN))
(GETB (LASTELE C) 'DEFN]
(FORGET-CONCEPT GTEMP12)
(CPRIN1S 8 GTEMP12 turned out to be equivalent to GTEMP308 DCR)$$
A conditional print statement. If the verbosity level is high enough
(>8), this message is typed out to the user. Note the intermixing of
variables (e.g., "GTEMP308") and undefined atoms (e.g.,
"equivalent"). CPRIN1S examines each argument, and if it is
undefined, it quotes it. $
GTEMP308)
(T (INCRB GUP1 'EXS (NCONC1 (GEARGS GUP1) GTEMP12))
[SOME (RIPPLE GUP1 'GENL)
(FUNCTION (LAMBDA (G)
(SOME (GETB G 'D-R)
(FUNCTION (LAMBDA (D)
(AND (ISA BA1 (CAR D))
(ISA BA2 (CADR D))
(INCRB GTEMP12 'UP$$ The ISA's facet
is called "UP" in the LISP program. $ (CADDR D))
(INCRB (CADDR D) 'EXS GTEMP12]
(* This last INCRB says that if an operation f maps onto range C,
and we apply f and get a new Being, then that Being ISA C)$$ This
is
a streamlined, specialized version of the more general
heuristic rule number {[3]GETRR}; see page {[3]GETRRP}. $
(INCRB GTEMP12 'IN-RAN-OF GUP1)
(INCRB BA2 'IN-DOM-OF GUP1)
(INCRB BA1 'IN-DOM-OF GUP1)
(* Now see if the composition GTEMP12 shares any ISA's entries with
either constituent operation: BA1 or BA2)$$
This next MAPC is thus the LISP encoding of heuristic rule number {[3]ISARG};
see page {[3]ISARGP}. $
.ISARGP2: PAGE;
[MAPC [INTERSECTION (SET-DIFF [UNION (GETB BA1 'UP) (GETB BA2 'UP]
(GETB GTEMP12 'UP]
(FUNCTION (LAMBDA (Z)
(COND
((DEFN Z GTEMP12)
(INCRB Z 'EXS GTEMP12)
(INCRB GTEMP12 'UP Z]
(COND
[(GETB GTEMP12 'UP)
(SETB GTEMP12 'GUP (COPY (GETB GTEMP12 'UP]
(T (INCRB GTEMP12 'UP 'OPERATION)
(INCRB 'OPERATION 'EXS GTEMP12)))
& (* A similar search now for GENL/SPEC of the composition)
(SETB GTEMP12 'D-R (CAR GTEMP11))
(INCRB GTEMP12 'ALGS
(LIST 'TYPE 'NONRECURSIVE 'APPLICATION 'OF GUP1 (CADR GTEMP11)))
& (* Code for synthesizing a Defn entry for GTEMP12)
(SETB GTEMP12 'WORTH
(MAP2CAR (GETB BA1 'WORTH) (GETB BA2 'WORTH) 'TIMES1000))
(GS-CHECK$$
This is a general-purpose function for testing that there is no hidden
cycle in the Generalization network, that no two concepts are both
generalizations and specializations of each other, unless they are tagged
as being equivalent to each other. $ GTEMP12]]))]
⊗4Appearance on page {[3]COMPP}:⊗*
.WBOX(8,8)
MBOX Algorithms: $
MBOX Distributed: use the heuristics attached to Compose to guide the filling $
MBOX in of various facets of the new composition. $
FBOX (The heuristics referred to are shown in Appendix {[3]ALLHEU}.{[3]COMPH}, on page {[3]COMPHP}.) %
MBOX Fillin: 5 ⊗4(out of a total of 9)⊗* heuristics. $
MBOX Check: 1 heuristic ⊗4(out of a total of 2)⊗* $
.EBOX
.APART; GROUP;
⊗5↓_UP_↓⊗* (OPERATION)
⊗4Appearance on page {[3]COMPP}:⊗*
.WBOX(8,8)
MBOX Isa's: Operation $
.EBOX
.APART; GROUP;
⊗5↓_WORTH_↓⊗* (300)
⊗4Appearance on page {[3]COMPP}:⊗*
.WBOX(8,8)
MBOX Worth: 300 $
.EBOX
.APART
⊗5↓_INT_↓⊗*$$
Note that although the Fillin and Suggest heuristics are blended into the
relevant facets (e.g., into the Algorithms for COMPOSE), the INTERESTINGNESS
type heuristics are kept separate, in this facet. $ [(IMATRIX (1 2 3) (4 5))
(COND [(INTERSECTION (MAPAPPEND (GETB BA2 'D-R) 'LAST)
(MAPAPPEND (GETB BA1 'D-R) 'ALL-BUT-LAST))
300
(IDIFF 400 (ITIMES 100 (IPLUS (LENGTH (GETB BA1 'D-R))
(LENGTH (GETB BA2 'D-R]
(REASON (* In some interpretation, Range-of-op2 is 1 component of Domain-of-op1)))
(COND [[MEMB [CAR (LAST (CAR (GETB BA2 'D-R]
(ALL-BUT-LAST (CAR (GETB BA1 'D-R]
400
(IDIFF 1000 (ITIMES 100 (LENGTH (CAR (GETB BA1 'D-R]
(REASON (* In canonical interpretation, Range-of-op2 is a component of Domain of op1)))
(COND [(INTERSECTION (GETB CS-B TIES)
(UNION (GETB BA1 TIES)(GETB BA2 TIES)))
100
(ITIMES 100 [LENGTH (INTERSECTION (GETB CS-B TIES)
(UNION (GETB BA1 TIES)(GETB BA2 TIES])
(REASON (* This composition preserves some good properties of its constituents))])
(COND [(SET-DIFFERENCE (GETB CS-B TIES)
(UNION (GETB BA1 TIES)(GETB BA2 TIES)))
100
(ITIMES 100 [LENGTH (SET-DIFFERENCE (GETB CS-B TIES)
(UNION (GETB BA1 TIES)(GETB BA2 TIES])
(REASON (* This composition has some new props, not true of either constituent))])
(COND [(OR (GREATERP (GETB BA1 'WORTH) 500))
(GREATERP (GETB BA2 'WORTH) 500)))
300
(IQUOTIENT (ITIMES (GETB BA1 'WORTH)(GETB BA2 'WORTH))
1000)
(REASON (* Op1 and/or Op2 are very interesting themselves))])
(COND [[IS-ONE-OF [CAR (LAST (CAR (GETB BA2 'D-R]
(ALL-BUT-LAST (CAR (GETB BA1 'D-R]
350
(IDIFF [ITIMES 100 (IDIFF
[LENGTH (CAR (GETB BA1 'D-R]
(LENGTH (RIPPLE [IS-ONE-OF
[SETQ TMP4 (CAR (LAST (GETB BA2 'D-R]
(ALL-BUT-LAST (CAR (GETB BA1 'D-R]
'GENL]
(ITIMES 50 (LENGTH (RIPPLE TMP4 'GENL]
(REASON (* In canonical interpretation, Range-of-op2 is a specialization of a component
of Domain-of-op1)))
(COND [[MEMB [CAR (LAST (CAR (GETB BA1 'D-R]
(ALL-BUT-LAST (CAR (GETB BA2 'D-R]
450
(IPLUS 300 (COND ([MEMB [CAR (LAST (CAR (GETB BA1 'D-R]
(ALL-BUT-LAST (CAR (GETB BA1 'D-R]
10)
(T 250))
(COND ([MEMB [CAR (LAST (CAR (GETB BA2 'D-R]
(ALL-BUT-LAST (CAR (GETB BA2 'D-R]
11)
(T 250))
(ITIMES 70 (LENGTH (RIPPLE [CAR (LAST (CAR (GETB BA1 'D-R] 'GENL]
(REASON (* In canonical interpretation,
Range-of-op1 is one component of Domain-of-op2))
&
(COND [[ISA [CAR (LAST (CAR (GETB BA1 'D-R]
(ALL-BUT-LAST (CAR (GETB BA2 'D-R]
250
(IPLUS 50 (COND ([ISA [CAR (LAST (CAR (GETB BA1 'D-R]
(ALL-BUT-LAST (CAR (GETB BA1 'D-R]
10)
(T 100))
(COND ([ISA [CAR (LAST (CAR (GETB BA2 'D-R]
(ALL-BUT-LAST (CAR (GETB BA2 'D-R]
11)
(T 100))
(ITIMES 50 (LENGTH (RIPPLE [CAR (LAST (CAR (GETB BA1 'D-R] 'GENL]
(REASON (* Range-of-op1 is a specialization of a component of Domain-of-op2]
⊗4Appearance on page {[3]COMPP}:⊗*
.WBOX(8,8)
MBOX Interest: 11 heuristics. $
FBOX The heuristic rules encoded above are shown in English on page {[3]COMI}. %
.EBOX
.TURN ON "∞→"; SELECT 8
∞≡→
⊗4Here is the code for CON-MERGE-ARGS, the function which decides how to overlap
the domain/range facets of its two arguments, F1 and F2:⊗*
.SELECT 7; CONMERGEP: PAGE;
(CON-MERGE-ARGS
[LAMBDA (F1 F2 F12 PGM1 SCHK SAPL DOM1 DOM2 RAN1 RAN2 TIL DOM3)
[SETQ RAN1 (LAST (CAR (GETB F1 'D-R]
(SETQ DOM1 (LDIFF (CAR (GETB F1 'D-R))
RAN1))
[SETQ RAN2 (LAST (CAR (GETB F2 'D-R]
(SETQ DOM2 (LDIFF (CAR (GETB F2 'D-R))
RAN2))
[SETQ DOM3 (AND (CDR DOM1)
(LIST (CADR (MIN2 (APPEND RAN2 RAN2 RAN2
RAN2) DOM1 'FRAC-OVERLAP]
(* As DOMi and RANi are located, Switching of Args may be required, inside PGM1)
(AND (MEMB (CAR DOM3) DOM2) (SETQ DOM3 NIL))
(SETQ GTEMP20 (LENGTH DOM2))
[SETQ SAPL (NCONC (LIST 'APPLYB (KWOTE F1) (Q ALGS))
(MAPCAR (SUB-ONCE 'X
[SETQ GTEMP19 (COND
((IS-ONE-OF (CAR RAN2) DOM1))
[(SETQ SCHK (ONE-ISAG DOM1 (CAR RAN2]
((SETQ SCHK (AND (SETQ TIL (EXS (CAR RAN2))
(CAR (SOME DOM1 (FUNCTION (LAMBDA (D)
(INTERSECTION
TIL
(EXS D]
DOM1)
(FUNCTION (LAMBDA (Z)
(COND
((EQ Z 'X)
'X)
(T (SETQ GTEMP20 (ADD1 GTEMP20))
(CAR (FNTH BA-LIST GTEMP20]
(* SCHK is a flag which means that f2 maps us into an element of RAN2 which is not guaranteed
a priori to be an element of DOM1, hence a check for this applicability of f1 will then have to be made)
(COND
((FMEMB 'X SAPL)
(SETQ DOM3 (REM-ONCE GTEMP19 DOM1))
(SETQ GTEMP7 (APPEND DOM3 DOM2))
[COND
[(NEQ (LENGTH GTEMP7)
(LENGTH (SELF-INT GTEMP7)))
(CPRIN1S 9 CRLF CRLF AM can later coalesce the D-R of F12 DCR)
[ADD-CANDS (LIST (LIST (LIST 'APPLYB (Q COALESCE) (Q ALGS) (KWOTE F12))
(IPLUS 100 (IQUO (DOTPROD (FIRSTN 2 (GETB F1 'WORTH))
(GETB F2 'WORTH)) 2000))
(LIST (SPLIST There is an overlap in the new combined
domain of the operation F12]
(SWHY 9 (There is an obvious overlap in (@ GTEMP7),the new combined domain of (@ F12]
⊗4The next piece of this function is the heuristic rule numbered {[3]COAC} in Appendix {[2]ALLHEU}.⊗*
([SOME GTEMP7 (FUNCTION (LAMBDA (X)
(IS-ONE-OF X (CDR (FMEMB X GTEMP7]
(CPRIN1S 10 CRLF CRLF AM may later coalesce the D-R of F12 DCR)
[ADD-CANDS (LIST (LIST (LIST 'APPLYB (Q COALESCE) (Q ALGS) (KWOTE F12))
(IQUO (DOTPROD (FIRSTN 2 (GETB F1 'WORTH))
(GETB F2 'WORTH)) 2500))
(LIST (SPLIST There may be an overlap
in the new combined domain of the operation F12]
(SWHY 10 (There is a subtle overlap in (@ GTEMP7),the new combined domain of (@ F12]
[SETQ PGM1 (LIST 'PROG
(LIST 'X)
[LIST 'SETQ 'X
(NCONC (LIST 'APPLYB (KWOTE F2) (Q ALGS))
(FIRSTN (LENGTH DOM2) (LIST 'BA1 'BA2 'BA3]
(LIST 'RETURN
(COND
(SCHK (LIST 'AND
(LIST 'APPLY* (Q DEFN) (KWOTE SCHK) 'X)
SAPL))
(T (LIST 'AND 'X SAPL]
(LIST (LIST (APPEND DOM2 DOM3 RAN1)) PGM1))
(T (* Composing is not possible) NIL])
.E
<<Should there be more explanation of the bits of this code? >
.SELECT 1;
. SKIP TO COLUMN 1; ASSSEC(The `Osets' Concept)
Here is the actual property list of the data-structure corresponding to the
Osets concept:
.TURN ON "{}";
.BEGIN NOFILL PREFACE 0; INDENT 0; SELECT 3; TURN OFF "@"; GROUP;
⊗5↓_ENGN_↓⊗* (OSET Oset Oset-structure OSET-STRUC, Ordered-set (Set))
⊗5↓_DEFN_↓⊗* (TYPE NEC&SUFF RECURSIVE TRANSPARENT [COND
((EQUAL BA1 (OSET )) T)
(T (APPLYB 'OSET 'DEFN (APPLYB 'OSET-DELETE 'ALGS
(APPLYB 'SOME-MEMB 'ALGS BA1)
BA1])
(TYPE NEC&SUFF RECURSIVE QUICK [COND
((EQUAL BA1 '(OSET )) T)
((CDDR BA1) (APPLYB 'OSET 'DEFN (RPLACD BA1 (CDDR BA1)))
(T NIL])
(TYPE NEC&SUFF NONRECURSIVE QUICK (MATCH BA1 WITH ('OSET $)))
⊗5↓_GENL_↓⊗* (ORD-STRUC NO-MULT-ELES-STRUC)
⊗5↓_WORTH_↓⊗* (400)
⊗5↓_IN-DOM-OF_↓⊗* (OSET-JOIN OSET-INTERSECT OSET-DIFF OSET-INSERT OSET-DELETE)
⊗5↓_IN-RAN-OF_↓⊗* (OSET-JOIN OSET-INTERSECT OSET-DIFF OSET-INSERT OSET-DELETE)
⊗5↓_VIEW_↓⊗* (STRUCTURE (RPLACA BA1 'OSET))
.ES;
Compare this with the
way that the "Osets" concept appeared, on page {[3]OSETCP} of
Appendix {[3]ALLCON}.1:
.GROUP SKIP 1; WBOX(8,8);
MBOX Name(s): Oset, Oset-structure, Ordered-set, sometimes: Set. $
MBOX Definitions: $
MBOX Recursive: λ (S) (S=[ ] or Oset.Definition(Oset-Delete.Alg(Member.Alg(S),S))) $
MBOX Recursive quick: λ (S) (S=[ ] or Oset.Definition (CDR(S))) $
MBOX Quick: λ (S) (Match S with [...] ) $
MBOX Generalizations: Ordered-Structure, No-multiple-elements-Structure $
MBOX Worth: 400 $
MBOX In-domain-of: Oset-union, Oset-intersect, Oset-difference, Oset-insert, Oset-delete $
MBOX In-range-of: Oset-union, Oset-intersect, Oset-difference, Oset-insert, Oset-delete $
MBOX View: To view any structure as a Oset, do: λ (x) Enclose-in-square-brackets(x) $
.EBOX
.E
.ASSECP(Concepts created by AM)
The list below is meant to suggest the range of AM's definitions; it
is far from complete, and most of the omissions were real losers.
The concepts are listed in the order in which they were defined.$$
See Appendix {[2]TRACES}.{[2]TRATS}, p. {[3]TRAT}, for a detailed
trace of how these concepts were discovered. Or see Section
{[2]RESULT}.{[2]SHORTASK}, p. {[3]SHORTASKP}, for a briefer version
of the same development. $ In place of the (usually-awkward) name
chosen by AM, I have given either the standard math/English name for
the concept, or else a short description of what it is.
.NEWCLIST: PAGE;
.BEGIN NOFILL PREFACE 0 SELECT 1; INDENT 0;
Sets with less than 2 elements (singletons and empty sets).
Sets with no atomic elements (nests of braces).
Singleton sets.
Bags containing (multiple occurrences of) just one kind of element.
Superset (contains).
Doubleton bags and sets.
Set-membership.
Disjoint bags.
Subset.
Disjoint sets.
Singleton osets.
Same-length (same number of elements).
Same number of left parentheses, plus identical leftmost atoms.
Count (find the number of elements of a given structure).
Numbers (unary representation).
Add.
Minimum.
SUB1 (λ (x) x-1).
Insert x into a given Bag-of-T's (almost ADD1, but not quite).
Subtract (except: if x<y, then the result of x-y will be zero$$
This is "natural-number subtract", in the same spirit of naming as we find for
"Integer division". $).
Less than or equal to.
Times.
Union of a ⊗4bag⊗* of structures.
& (the ampersand represents the creation of several real losers.)
Compose a given operation F with itself (form F-o-F).
Insert structure S into itself.
Try to delete structure S from itself (a loser).
Double (add `x' to itself).
Subtract `x' from itself (as an operation, this is a real zero$$ a natural zero? $).
Square (TIMES(x,x)).
Union structure S with itself.
Coalesced-replace2: replace each element s of S by F(s,s).
Coalesced-join2: append together F(s,s), for each member s⊗6ε⊗*S.
Coa-repeat2: create a new op which takes a struc S, op F, and repeats F(s,t,S) all along S.
Compose three operations: λ(F,G,H) F-o-(G-o-H).
Compose three operations: λ(F,G,H) (F-o-G)-o-H.
& (lots of losing compositions created, e.g. Self-insert-o-Set-union.)
ADD-1-(x): all ways of representing x as the sum of a bunch of nonzero numbers.
G-o-H, s.t. H(G(H(x))) is always defined (wherever H is), and G and H are interesting.
Insert-o-Delete.
Delete-o-Insert.
Size-o-ADD-1-. (λ (n) The number of ways to partition n)
Cubing
&
Exponentiation.
Halving (in natual numbers only; thus Halving(15)=7).
Even numbers.
Integer square-root.
Perfect squares.
Divisors-of.
Numbers-with-0-divisors.
Numbers-with-α1-divisor.
Primes (Numbers-with-2-divisors).
Squares of primes (Numbers-with-3-divisors).
Squares of squares of primes.
Square-roots of primes (a loser).
TIMES-1-(x): all ways of representing x as the product of a bunch of numbers (>1).
All ways of representing x as the product of just one number (a trivial notion).
All ways of representing x as the product of primes.
All ways of representing x as the sum of primes.
All ways of representing x as the sum of two primes.
Numbers uniquely representable as the sum of two primes.
Products of squares.
Multiplication by 1.
Multiplication by 0.
Multiplication by 2.
Addition of 0.
Addition of 1.
Addition of 2.
Product of even numbers.
Sum of squares.
Sum of even numbers.
& (losers: various compositions of 3 operations.)
Pairs of perfect squares whose sum is also a perfect square (x↑2+y↑2=z↑2).
Prime pairs (p,p+2 are prime).
⊗8 # # #⊗*
.E